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

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP Harvard University]

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

4
00:00:08,000 --> 00:00:11,730
Bubble Sort je príklad triedenie algoritmu -

5
00:00:11,730 --> 00:00:14,460
to znamená, že postup pre triedenie sadu prvkov v

6
00:00:14,460 --> 00:00:15,840
vzostupne alebo zostupne.

7
00:00:15,840 --> 00:00:18,710
Napríklad, ak ste chceli triediť pole skladajúci sa z čísel

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], by správne vykonávanie Bubble Zoradiť vráti

9
00:00:23,060 --> 00:00:26,260
zoradené pole [2, 3, 5, 9] vo vzostupnom poradí.

10
00:00:26,260 --> 00:00:28,850
Teraz, budem vysvetľovať v pseudokódu, ako algoritmus funguje.

11
00:00:28,850 --> 00:00:34,000
>> Povedzme, že máme radenie zoznamu celých čísel 5 - 3, 2, 9, 6, a 5.

12
00:00:34,000 --> 00:00:37,650
Algoritmus začína pri pohľade na prvé dva prvky, 3 a 2,

13
00:00:37,650 --> 00:00:40,850
a kontrolovať, či sú mimo prevádzky vzhľadom k sebe.

14
00:00:40,850 --> 00:00:43,150
Sú - 3 je väčší ako 2.

15
00:00:43,150 --> 00:00:45,190
Ak chcete byť vo vzostupnom poradí, mali by byť iná cesta okolo.

16
00:00:45,190 --> 00:00:46,610
Takže, vymeníme ich.

17
00:00:46,610 --> 00:00:49,760
Teraz zoznam vyzerá nasledovne: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Ďalej sa pozrieme na druhej a tretej prvkov, 3 a 9.

19
00:00:52,450 --> 00:00:55,770
Sú v správnom poradí vzhľadom k sebe navzájom.

20
00:00:55,770 --> 00:00:58,800
To znamená, že 3 je menší ako 9 tak, že algoritmus nie je vymeniť je.

21
00:00:58,800 --> 00:01:01,900
Ďalej sa pozrieme na 9 a 6. Sú mimo prevádzky.

22
00:01:01,900 --> 00:01:04,260
>> Takže, musíme vymeniť, pretože 9 je väčší ako 6.

23
00:01:04,260 --> 00:01:08,840
Konečne sa pozrieme na posledných dvoch celých čísel, 9 a 5.

24
00:01:08,840 --> 00:01:10,850
Sú mimo prevádzky, a preto musí byť vymenený.

25
00:01:10,850 --> 00:01:13,360
Po prvom kompletnom prechode zoznamu,

26
00:01:13,360 --> 00:01:17,140
vyzerá nasledovne: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Nie je to zlé. Je to skoro zoradené.

28
00:01:19,690 --> 00:01:22,450
Ale musíme prejsť zoznam znova, aby si to úplne zoradené.

29
00:01:22,450 --> 00:01:29,250
Dva je menší ako 3, takže nie vymeniť je.

30
00:01:29,250 --> 00:01:31,700
>> Tri je menšie ako 6, takže nie vymeniť je.

31
00:01:31,700 --> 00:01:35,500
Šesť je väčší ako 5. My vymenili.

32
00:01:35,500 --> 00:01:38,460
Šesť je menšia ako 9. Nechceme vymeniť.

33
00:01:38,460 --> 00:01:42,170
Po druhom prechode, to vyzerá takto: [2, 3, 5, 6, 9]. Perfect.

34
00:01:42,170 --> 00:01:44,680
Teraz, poďme napísať, že v pseudokódu.

35
00:01:44,680 --> 00:01:48,450
V podstate, pre každý prvok v zozname, musíme sa na to pozrieť

36
00:01:48,450 --> 00:01:50,060
a prvok priamo k jeho pravej strane.

37
00:01:50,060 --> 00:01:53,420
Ak sú mimo prevádzky vo vzťahu k sebe - to znamená, že v prípade, že prvok vľavo

38
00:01:53,420 --> 00:01:56,810
je väčší ako na pravej strane - by sme mali vymeniť dva prvky.

39
00:01:56,810 --> 00:02:01,270
>> Robíme to pre každý prvok zoznamu, a urobili sme jeden priechod cez.

40
00:02:01,270 --> 00:02:05,160
Teraz len musíme robiť pass-through toľkokrát, aby zoznam

41
00:02:05,160 --> 00:02:06,480
je plne riadne zoradené.

42
00:02:06,480 --> 00:02:08,889
Ale koľkokrát musíme prejsť v zozname

43
00:02:08,889 --> 00:02:10,400
zaručiť, že sme urobili?

44
00:02:10,400 --> 00:02:14,730
No, najhorší scenár je, ak budeme mať úplne dozadu zoznam.

45
00:02:14,730 --> 00:02:17,840
Potom sa množstvo zložiť priechodiek, ktorá sa rovná počtu

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

47
00:02:19,730 --> 00:02:24,720
Ak to nedáva zmysel intuitívne, myslieť na jednoduchom prípade - zoznam [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> To bude trvať jeden pass-through triediť správne.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - V najhoršom prípade, že sa 3 prvky zoradené dozadu,

50
00:02:33,060 --> 00:02:34,830
to bude trvať 2 iterácií zoradiť.

51
00:02:34,830 --> 00:02:37,980
Po jednej iterácie, je to [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Druhý výnosy zoradené pole [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Takže viete, že nikdy nebudete musieť ísť cez pole, všeobecne,

54
00:02:43,350 --> 00:02:46,790
viac než n-1 krát, kde n je počet prvkov v poli.

55
00:02:47,090 --> 00:02:50,470
Je to tzv Bubble Sort, pretože najväčšie prvky majú tendenciu "bubble-up"

56
00:02:50,470 --> 00:02:51,950
doprava celkom rýchlo.

57
00:02:51,950 --> 00:02:53,980
V skutočnosti, tento algoritmus má veľmi zaujímavé správanie.

58
00:02:53,980 --> 00:02:57,410
>> Po m iteráciách cez celé pole,

59
00:02:57,410 --> 00:02:59,000
najviac vpravo m prvky sú zaručené

60
00:02:59,000 --> 00:03:01,000
ktoré majú byť triedené do ich správne miesto.

61
00:03:01,000 --> 00:03:02,280
Ak chcete vidieť to pre seba,

62
00:03:02,280 --> 00:03:05,500
môžeme vyskúšať na úplne dozadu zozname [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Po jednom prechode celého zoznamu,

64
00:03:08,220 --> 00:03:09,220
[Zvuk písania]

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
úplne vpravo element 9 je na svojom mieste.

67
00:03:21,250 --> 00:03:24,760
Po druhom pass-through, bude mať 6 "bublala-up" na

68
00:03:24,760 --> 00:03:26,220
druhej nejpravější miesto.

69
00:03:26,220 --> 00:03:28,840
Tieto dva prvky na pravej strane - 6 a 9 - bude v ich správnych miestach

70
00:03:28,840 --> 00:03:30,580
po prvých dvoch Pass-priechodiek.

71
00:03:30,580 --> 00:03:32,590
>> Takže, ako môžeme použiť na optimalizáciu algoritmu?

72
00:03:32,590 --> 00:03:34,850
No, po jednej iterácie cez pole

73
00:03:34,850 --> 00:03:37,690
nemáme vlastne treba skontrolovať úplne vpravo prvok

74
00:03:37,690 --> 00:03:39,200
pretože vieme, že to sú zoradené.

75
00:03:39,200 --> 00:03:43,050
Po dvoch iteráciách, vieme určite najviac vpravo dva prvky sú na svojom mieste.

76
00:03:43,050 --> 00:03:48,260
Takže, všeobecne po kv iteráciách cez celú radom,

77
00:03:48,260 --> 00:03:51,550
Kontrola poslednej K prvkov je nadbytočná, pretože vieme,

78
00:03:51,550 --> 00:03:52,360
sú na správnom mieste už.

79
00:03:52,360 --> 00:03:54,870
>> Takže ak ste triedenie poľa n prvkov,

80
00:03:54,870 --> 00:03:57,870
na prvú iteráciu - budeš musieť roztriediť všetky prvky - prvý N-0.

81
00:03:57,870 --> 00:04:04,170
Na druhej iterácii, budete sa musieť pozrieť na všetky prvky, ale posledný -

82
00:04:04,170 --> 00:04:07,090
prvých n-1.

83
00:04:07,090 --> 00:04:10,520
Ďalšie optimalizácia môže byť zistiť, či je zoznam už je zoradený

84
00:04:10,520 --> 00:04:11,710
po každej iterácii.

85
00:04:11,710 --> 00:04:13,900
Ak je to už je zoradený, nepotrebujeme, aby sa žiadne ďalšie iterácie

86
00:04:13,900 --> 00:04:15,310
v zozname.

87
00:04:15,310 --> 00:04:16,220
Ako to môžeme urobiť?

88
00:04:16,220 --> 00:04:19,360
No, ak nebudeme robiť žiadne swapy na premietanie v zozname,

89
00:04:19,360 --> 00:04:22,350
je jasné, že zoznam bol už je zoradený, pretože sme nemali zameniť nič.

90
00:04:22,350 --> 00:04:24,160
Takže sme rozhodne nemusíme radiť znova.

91
00:04:24,160 --> 00:04:27,960
>> Možno by ste mohli inicializovať vlajky premennú s názvom "nie je zoradená" na

92
00:04:27,960 --> 00:04:30,990
false a zmeniť ho na hodnotu true, ak máte vymeniť akékoľvek prvky na

93
00:04:30,990 --> 00:04:32,290
jedna iterácia cez pole.

94
00:04:32,290 --> 00:04:35,350
Alebo podobne, aby sa počítadlo počítať, koľko swapy urobíte

95
00:04:35,350 --> 00:04:37,040
na danej iterácii.

96
00:04:37,040 --> 00:04:40,040
Na konci iterácie, ak nebola vymeniť niektorý z prvkov,

97
00:04:40,040 --> 00:04:41,780
viete, zoznam je už zoradená a máte hotovo.

98
00:04:41,780 --> 00:04:44,090
Bubble Sort, rovnako ako ostatné metódy radenia, môže byť

99
00:04:44,090 --> 00:04:46,960
vylepšený pracovať pre všetky prvky, ktoré majú usporiadanie metódy.

100
00:04:46,960 --> 00:04:50,610
>> To je vzhľadom k tomu, dva prvky máte spôsob, ako povedať, ak prvý

101
00:04:50,610 --> 00:04:53,770
je väčšia než, rovný alebo menší ako druhé.

102
00:04:53,770 --> 00:04:56,870
Napríklad by ste mohli radiť písmená abecedy vyslovením

103
00:04:56,870 --> 00:05:00,520
že a <b, b <c, atď

104
00:05:00,520 --> 00:05:03,830
Alebo by ste mohli radiť dni v týždni, kedy je nedeľa menej do pondelka

105
00:05:03,830 --> 00:05:05,110
ktorá je menšia než utorok.

106
00:05:05,110 --> 00:05:09,630
>> Bubble Sort nie je v žiadnom prípade veľmi efektívne, alebo rýchlo triedenie algoritmus.

107
00:05:09,630 --> 00:05:12,370
Jeho najhoršie runtime je Big O n ²

108
00:05:12,370 --> 00:05:14,810
pretože budete musieť vykonať n iterácií pomocou zoznamu

109
00:05:14,810 --> 00:05:18,430
kontrolu všetkých n prvkov každej pass-through, NXN = n ².

110
00:05:18,430 --> 00:05:22,730
To beží čas znamená, že počet prvkov ste triedenie zvýšenie,

111
00:05:22,730 --> 00:05:24,330
doba chodu zvyšuje kvadraticky.

112
00:05:24,330 --> 00:05:27,330
>> Ale ak účinnosť nie je veľkým problémom vášho programu

113
00:05:27,330 --> 00:05:29,550
alebo ak ste len radenie malý počet prvkov,

114
00:05:29,550 --> 00:05:31,660
môžete nájsť Bubble Sort užitočné, pretože

115
00:05:31,660 --> 00:05:33,360
je to jedna z najjednoduchších algoritmov triedenia pochopiť

116
00:05:33,360 --> 00:05:34,250
a kód.

117
00:05:34,250 --> 00:05:37,270
Je to tiež skvelý spôsob, ako získať skúsenosti s prekladaním teoretické

118
00:05:37,270 --> 00:05:40,220
algoritmus do skutočného fungovania kódu.

119
00:05:40,220 --> 00:05:43,000
No, to je Bubble Sort pre vás. Vďaka za sledovanie.

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