1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [SORT BUBBLE]

2
00:00:02,840 --> 00:00:04,560
[JACKSON Steinkamp Universitatea Harvard]

3
00:00:04,560 --> 00:00:07,500
[THIS IS CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Sortare Bubble este un exemplu de algoritm de sortare -

5
00:00:11,730 --> 00:00:14,460
că este, o procedură de sortare un set de elemente în

6
00:00:14,460 --> 00:00:15,840
ordine crescătoare sau descrescătoare.

7
00:00:15,840 --> 00:00:18,710
De exemplu, dacă ai vrut să sortați o matrice format din numere

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], o punere în aplicare corectă a după Bubble ar reveni

9
00:00:23,060 --> 00:00:26,260
matrice sortate [2, 3, 5, 9], în ordine crescătoare.

10
00:00:26,260 --> 00:00:28,850
Acum, am de gând să explice în pseudocod algoritmul functioneaza cum.

11
00:00:28,850 --> 00:00:34,000
>> Să spunem că te sortarea o listă de 5 intregi - 3, 2, 9, 6, și 5.

12
00:00:34,000 --> 00:00:37,650
Algoritmul începe uitandu-se la primele două elemente, 3 și 2,

13
00:00:37,650 --> 00:00:40,850
și verificarea dacă sunt în ordine față de celălalt.

14
00:00:40,850 --> 00:00:43,150
Acestea sunt - 3 este mai mare de 2.

15
00:00:43,150 --> 00:00:45,190
Pentru a fi în ordine crescătoare, acestea ar trebui să fie invers.

16
00:00:45,190 --> 00:00:46,610
Deci, i-am schimba.

17
00:00:46,610 --> 00:00:49,760
Acum, lista arată astfel: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> În continuare, ne uităm la elementele doilea și al treilea, 3 și 9.

19
00:00:52,450 --> 00:00:55,770
Sunt în ordinea corectă față de celălalt.

20
00:00:55,770 --> 00:00:58,800
Asta este, 3 este mai mică de 9, astfel algoritmul nu le schimba.

21
00:00:58,800 --> 00:01:01,900
În continuare, ne uităm la 9 și 6. Sunt de ordine.

22
00:01:01,900 --> 00:01:04,260
>> Deci, avem nevoie de a le schimba, deoarece 9 este mai mare de 6.

23
00:01:04,260 --> 00:01:08,840
În cele din urmă, ne uităm la ultimele două numere întregi, 9 și 5.

24
00:01:08,840 --> 00:01:10,850
Sunt de ordine, astfel încât acestea trebuie să fie schimbate.

25
00:01:10,850 --> 00:01:13,360
După trecere completă prin prima listă,

26
00:01:13,360 --> 00:01:17,140
se pare ca acest lucru: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Nu-i rău. E aproape sortate.

28
00:01:19,690 --> 00:01:22,450
Dar avem nevoie pentru a rula prin lista din nou să-l complet sortate.

29
00:01:22,450 --> 00:01:29,250
Doi este mai mică de 3, așa că nu le schimba.

30
00:01:29,250 --> 00:01:31,700
>> Trei este mai mică de 6, așa că nu le schimba.

31
00:01:31,700 --> 00:01:35,500
Sase este mai mare decât 5. Am schimbat.

32
00:01:35,500 --> 00:01:38,460
Sase este mai mică de 9. Noi nu schimba.

33
00:01:38,460 --> 00:01:42,170
Dupa a doua trecere prin, se pare ca aceasta: [2, 3, 5, 6, 9]. Eveniment.

34
00:01:42,170 --> 00:01:44,680
Acum, hai să-l scrie în pseudocod.

35
00:01:44,680 --> 00:01:48,450
Practic, pentru fiecare element în listă, trebuie să ne uităm la ea

36
00:01:48,450 --> 00:01:50,060
și elementul direct la dreptul său.

37
00:01:50,060 --> 00:01:53,420
În cazul în care acestea sunt în afara de ordine față de celălalt - că este, în cazul în care elementul de pe partea stângă

38
00:01:53,420 --> 00:01:56,810
este mai mare decât cea de pe dreapta - ar trebui să ne schimba cele două elemente.

39
00:01:56,810 --> 00:02:01,270
>> Noi facem acest lucru pentru fiecare element al listei, iar noi am făcut-o singură trecere prin.

40
00:02:01,270 --> 00:02:05,160
Acum trebuie doar să facă ori trec prin destule-pentru a asigura listă

41
00:02:05,160 --> 00:02:06,480
este complet, corect sortate.

42
00:02:06,480 --> 00:02:08,889
Dar cum de multe ori avem de a trece prin lista de la

43
00:02:08,889 --> 00:02:10,400
garanteze că am terminat?

44
00:02:10,400 --> 00:02:14,730
Ei bine, scenariul cel mai rău caz este dacă avem o listă complet invers.

45
00:02:14,730 --> 00:02:17,840
Apoi, este nevoie de un număr de pass-through egal cu numărul

46
00:02:17,840 --> 00:02:19,730
de elemente n-1.

47
00:02:19,730 --> 00:02:24,720
Dacă acest lucru nu are nici un sens intuitiv, cred că de un simplu caz - lista [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Acest lucru se întâmplă pentru a lua una de trecere pentru a sorta corect.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - cel mai grav caz este că, cu 3 elemente sortate invers,

50
00:02:33,060 --> 00:02:34,830
se va lua 2 iterații la fel.

51
00:02:34,830 --> 00:02:37,980
După un iterație, e [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Randamentele două matrice sortate [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Deci, știți că niciodată nu trebuie să treacă prin matrice, în general,

54
00:02:43,350 --> 00:02:46,790
mai mult n-1 de ori, unde n este numărul de elemente din matrice.

55
00:02:47,090 --> 00:02:50,470
Se numește după Bubble, deoarece cele mai mari elemente au tendința de a "balon-up"

56
00:02:50,470 --> 00:02:51,950
la dreapta destul de repede.

57
00:02:51,950 --> 00:02:53,980
De fapt, acest algoritm are un comportament foarte interesant.

58
00:02:53,980 --> 00:02:57,410
>> După ce m iterații prin matrice întregul,

59
00:02:57,410 --> 00:02:59,000
elementele din dreapta m sunt garantate

60
00:02:59,000 --> 00:03:01,000
care urmează să fie sortate în locul lor corectă.

61
00:03:01,000 --> 00:03:02,280
Dacă vrei să vezi asta pentru tine,

62
00:03:02,280 --> 00:03:05,500
putem încerca pe o listă complet în spate [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
După o singură trecere prin întreaga listă,

64
00:03:08,220 --> 00:03:09,220
[Sunet de scris]

65
00:03:09,220 --> 00:03:18,790
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
elementul cel mai din dreapta 9 este în locul său.

67
00:03:21,250 --> 00:03:24,760
După al doilea pass-through, 6 va avea "barbotat-up" la

68
00:03:24,760 --> 00:03:26,220
două din dreapta loc.

69
00:03:26,220 --> 00:03:28,840
Cele două elemente de pe dreapta - 6 și 9 - va fi în locurile lor corecte

70
00:03:28,840 --> 00:03:30,580
după primele două pass-through.

71
00:03:30,580 --> 00:03:32,590
>> Deci, cum putem folosi aceasta pentru a optimiza algoritmul?

72
00:03:32,590 --> 00:03:34,850
Ei bine, după o iterație prin matrice

73
00:03:34,850 --> 00:03:37,690
nu avem nevoie de fapt, pentru a verifica elementul cel mai din dreapta

74
00:03:37,690 --> 00:03:39,200
pentru că știm că e sortate.

75
00:03:39,200 --> 00:03:43,050
După două iterații, știm sigur că din dreapta două elemente sunt la locul lor.

76
00:03:43,050 --> 00:03:48,260
Deci, în general, după iterații k prin matrice completă,

77
00:03:48,260 --> 00:03:51,550
verificarea elementelor ultimele k este redundantă, deoarece știm

78
00:03:51,550 --> 00:03:52,360
ei sunt în locația corectă deja.

79
00:03:52,360 --> 00:03:54,870
>> Deci, dacă sunteți de sortare o serie de elemente n,

80
00:03:54,870 --> 00:03:57,870
pe prima iterație - veti avea de a sorta toate elementele - primul n-0.

81
00:03:57,870 --> 00:04:04,170
La doua repetare, va trebui să se uite la toate elementele, dar ultima -

82
00:04:04,170 --> 00:04:07,090
prima n-1.

83
00:04:07,090 --> 00:04:10,520
O alta optimizare ar putea fi pentru a verifica dacă lista este sortată deja

84
00:04:10,520 --> 00:04:11,710
după fiecare iterație.

85
00:04:11,710 --> 00:04:13,900
Dacă este deja sortate, nu avem nevoie pentru a face mai multe iteratii orice

86
00:04:13,900 --> 00:04:15,310
prin listă.

87
00:04:15,310 --> 00:04:16,220
Cum putem face acest lucru?

88
00:04:16,220 --> 00:04:19,360
Ei bine, dacă nu vom face nici o swap pe un pass-through al listei,

89
00:04:19,360 --> 00:04:22,350
e clar că lista a fost deja sortate, deoarece nu am nimic schimb.

90
00:04:22,350 --> 00:04:24,160
Așa că nu avem cu siguranta pentru a sorta din nou.

91
00:04:24,160 --> 00:04:27,960
>> Poate că ai putea inițializa o variabilă de pavilion numit "nu sortate" pentru a

92
00:04:27,960 --> 00:04:30,990
falsă și schimba-l pe true dacă trebuie să schimbați orice elemente de pe

93
00:04:30,990 --> 00:04:32,290
o iterație prin matrice.

94
00:04:32,290 --> 00:04:35,350
Sau similar, fac un contor pentru a conta cât de multe swap faci

95
00:04:35,350 --> 00:04:37,040
pe orice iterație dat.

96
00:04:37,040 --> 00:04:40,040
La sfârșitul unei iterații, dacă nu schimbi oricare din elementele,

97
00:04:40,040 --> 00:04:41,780
Știi lista este deja sortate și ați terminat.

98
00:04:41,780 --> 00:04:44,090
Sortare bubble, la fel ca algoritmi de sortare alte, poate fi

99
00:04:44,090 --> 00:04:46,960
optimizat pentru a lucra pentru orice elemente care au o metodă prin care se dispune.

100
00:04:46,960 --> 00:04:50,610
>> Asta este, având în vedere două elemente ai un mod de a spune dacă prima

101
00:04:50,610 --> 00:04:53,770
este mai mare, egală sau mai mică decât cea de a doua.

102
00:04:53,770 --> 00:04:56,870
De exemplu, ai putea sorta litere ale alfabetului, spunând

103
00:04:56,870 --> 00:05:00,520
că a <b, b <c, etc

104
00:05:00,520 --> 00:05:03,830
Sau ai putea sorta zile ale săptămânii în care duminica este mai mică de luni

105
00:05:03,830 --> 00:05:05,110
care este mai puțin decât marți.

106
00:05:05,110 --> 00:05:09,630
>> Sortare bubble este în nici un caz un algoritm de sortare foarte eficient sau rapid.

107
00:05:09,630 --> 00:05:12,370
Sa cel mai rau caz rulare este Big O de n ²

108
00:05:12,370 --> 00:05:14,810
pentru că trebuie să facă iterații n printr-o listă

109
00:05:14,810 --> 00:05:18,430
verificarea tuturor elementelor n fiecare trecere, NxN = n ².

110
00:05:18,430 --> 00:05:22,730
Acest timp a alerga inseamna ca numarul de elemente ce te sortare crește,

111
00:05:22,730 --> 00:05:24,330
timpul de functionare creste quadratically.

112
00:05:24,330 --> 00:05:27,330
>> Dar dacă eficiența nu este o preocupare majoră a programului

113
00:05:27,330 --> 00:05:29,550
sau dacă sunteți de sortare doar un număr mic de elemente,

114
00:05:29,550 --> 00:05:31,660
s-ar putea găsi după Bubble util, deoarece

115
00:05:31,660 --> 00:05:33,360
este unul dintre cele mai simple algoritmi de sortare pentru a înțelege

116
00:05:33,360 --> 00:05:34,250
și pentru a coda.

117
00:05:34,250 --> 00:05:37,270
Este, de asemenea, o modalitate foarte bună de a obține experiență cu traducerea unui teoretică

118
00:05:37,270 --> 00:05:40,220
Algoritmul în codul funcționarea efectivă.

119
00:05:40,220 --> 00:05:43,000
Ei bine, asta e după Bubble pentru tine. Multumesc pentru vizionare.

120
00:05:43,000 --> 00:05:44,000
CS50.TV