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 příklad třídění algoritmu -

5
00:00:11,730 --> 00:00:14,460
to znamená, že postup pro třídění sadu prvků v

6
00:00:14,460 --> 00:00:15,840
vzestupně nebo sestupně.

7
00:00:15,840 --> 00:00:18,710
Například, pokud jste chtěli třídit pole skládající se z čísel

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], by správné provádění Bubble Seřadit vrátí

9
00:00:23,060 --> 00:00:26,260
seřazené pole [2, 3, 5, 9] ve vzestupném pořadí.

10
00:00:26,260 --> 00:00:28,850
Teď, budu vysvětlovat v pseudokódu, jak algoritmus funguje.

11
00:00:28,850 --> 00:00:34,000
>> Řekněme, že máme řazení seznamu celých čísel 5 - 3, 2, 9, 6, a 5.

12
00:00:34,000 --> 00:00:37,650
Algoritmus začíná při pohledu na první dva prvky, 3 a 2,

13
00:00:37,650 --> 00:00:40,850
a kontrolovat, zda jsou mimo provoz vzhledem k sobě.

14
00:00:40,850 --> 00:00:43,150
Jsou - 3 je větší než 2.

15
00:00:43,150 --> 00:00:45,190
Chcete-li být ve vzestupném pořadí, měly by být naopak.

16
00:00:45,190 --> 00:00:46,610
Takže, vyměníme je.

17
00:00:46,610 --> 00:00:49,760
Nyní seznam vypadá následovně: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Dále se podíváme na druhé a třetí prvků, 3 a 9.

19
00:00:52,450 --> 00:00:55,770
Jsou ve správném pořadí vzhledem k sobě navzájem.

20
00:00:55,770 --> 00:00:58,800
To znamená, že 3 je menší než 9 tak, algoritmus není vyměnit je.

21
00:00:58,800 --> 00:01:01,900
Dále se podíváme na 9 a 6. Jsou mimo provoz.

22
00:01:01,900 --> 00:01:04,260
>> Takže, musíme vyměnit, protože 9 je větší než 6.

23
00:01:04,260 --> 00:01:08,840
Konečně se podíváme na posledních dvou celých čísel, 9 a 5.

24
00:01:08,840 --> 00:01:10,850
Jsou mimo provoz, a proto musí být vyměněn.

25
00:01:10,850 --> 00:01:13,360
Po prvním kompletním průchodu seznamu,

26
00:01:13,360 --> 00:01:17,140
vypadá následovně: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Není to špatné. Je to skoro seřazeny.

28
00:01:19,690 --> 00:01:22,450
Ale musíme projít seznam znovu, aby si to úplně seřazeny.

29
00:01:22,450 --> 00:01:29,250
Dva je menší než 3, takže ne vyměnit je.

30
00:01:29,250 --> 00:01:31,700
>> Tři je menší než 6, takže ne vyměnit je.

31
00:01:31,700 --> 00:01:35,500
Šest je větší než 5. My vyměnili.

32
00:01:35,500 --> 00:01:38,460
Šest je menší než 9. Nechceme vyměnit.

33
00:01:38,460 --> 00:01:42,170
Po druhém průchodu, to vypadá takto: [2, 3, 5, 6, 9]. Perfect.

34
00:01:42,170 --> 00:01:44,680
Nyní, pojďme napsat, že v pseudokódu.

35
00:01:44,680 --> 00:01:48,450
V podstatě, pro každý prvek v seznamu, musíme se na to podívat

36
00:01:48,450 --> 00:01:50,060
a prvek přímo k jeho pravé straně.

37
00:01:50,060 --> 00:01:53,420
Pokud jsou mimo provoz ve vztahu k sobě - ​​to znamená, že v případě, že prvek vlevo

38
00:01:53,420 --> 00:01:56,810
je větší než na pravé straně - bychom měli vyměnit dva prvky.

39
00:01:56,810 --> 00:02:01,270
>> Děláme to pro každý prvek seznamu, a udělali jsme jeden průchod přes.

40
00:02:01,270 --> 00:02:05,160
Teď jen musíme dělat pass-through tolikrát, aby seznam

41
00:02:05,160 --> 00:02:06,480
je plně řádně seřazeny.

42
00:02:06,480 --> 00:02:08,889
Ale kolikrát musíme projít v seznamu

43
00:02:08,889 --> 00:02:10,400
zaručit, že jsme udělali?

44
00:02:10,400 --> 00:02:14,730
No, nejhorší scénář je, pokud budeme mít úplně dozadu seznam.

45
00:02:14,730 --> 00:02:17,840
Pak se množství složit průchodek, která se rovná počtu

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

47
00:02:19,730 --> 00:02:24,720
Pokud to nedává smysl intuitivně, myslet na jednoduchém případě - seznam [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> To bude trvat jeden pass-through třídit správně.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - v nejhorším případě je to, že se 3 prvky seřazeny dozadu,

50
00:02:33,060 --> 00:02:34,830
to bude trvat 2 iterací seřadit.

51
00:02:34,830 --> 00:02:37,980
Po jedné iterace, je to [2, 1, 3].

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

53
00:02:39,550 --> 00:02:43,350
Takže víte, že nikdy nebudete muset jít přes pole, obecně,

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

55
00:02:47,090 --> 00:02:50,470
Je to tzv. Bubble Sort, protože největší prvky mají tendenci k "bubble-up"

56
00:02:50,470 --> 00:02:51,950
doprava docela rychle.

57
00:02:51,950 --> 00:02:53,980
Ve skutečnosti, tento algoritmus má velmi zajímavé chování.

58
00:02:53,980 --> 00:02:57,410
>> Po m iteracích přes celé pole,

59
00:02:57,410 --> 00:02:59,000
nejvíce vpravo m prvky jsou zaručeny

60
00:02:59,000 --> 00:03:01,000
které mají být tříděny do jejich správné místo.

61
00:03:01,000 --> 00:03:02,280
Pokud chcete vidět to pro sebe,

62
00:03:02,280 --> 00:03:05,500
můžeme vyzkoušet na úplně dozadu seznamu [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Po jednom průchodu celého seznamu,

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

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
zcela vpravo element 9 je na svém místě.

67
00:03:21,250 --> 00:03:24,760
Po druhém pass-through, bude mít 6 "bublal-up" na

68
00:03:24,760 --> 00:03:26,220
druhé nejpravější místo.

69
00:03:26,220 --> 00:03:28,840
Tyto dva prvky na pravé straně - 6 a 9 - bude v jejich správných místech

70
00:03:28,840 --> 00:03:30,580
po prvních dvou Pass-průchodek.

71
00:03:30,580 --> 00:03:32,590
>> Takže, jak můžeme použít k optimalizaci algoritmu?

72
00:03:32,590 --> 00:03:34,850
No, po jedné iterace přes pole

73
00:03:34,850 --> 00:03:37,690
nemáme vlastně třeba zkontrolovat úplně vpravo prvek

74
00:03:37,690 --> 00:03:39,200
protože víme, že to jsou seřazena.

75
00:03:39,200 --> 00:03:43,050
Po dvou iteracích, víme jistě nejvíce vpravo dva prvky jsou na svém místě.

76
00:03:43,050 --> 00:03:48,260
Takže, obecně po kv iteracích přes celou řadou,

77
00:03:48,260 --> 00:03:51,550
Kontrola poslední K prvků je nadbytečná, protože víme,

78
00:03:51,550 --> 00:03:52,360
jsou na správném místě již.

79
00:03:52,360 --> 00:03:54,870
>> Takže pokud jste třídění pole n prvků,

80
00:03:54,870 --> 00:03:57,870
na první iteraci - budeš muset vyřešit všechny prvky - první N-0.

81
00:03:57,870 --> 00:04:04,170
Na druhé iteraci, budete se muset podívat na všechny prvky, ale poslední -

82
00:04:04,170 --> 00:04:07,090
prvních n-1.

83
00:04:07,090 --> 00:04:10,520
Další optimalizace může být zjistit, zda je seznam již řazeno

84
00:04:10,520 --> 00:04:11,710
po každé iteraci.

85
00:04:11,710 --> 00:04:13,900
Pokud je to již řazeno, nepotřebujeme, aby se žádné další iterace

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

87
00:04:15,310 --> 00:04:16,220
Jak to můžeme udělat?

88
00:04:16,220 --> 00:04:19,360
No, pokud nebudeme dělat žádné swapy na promítání v seznamu,

89
00:04:19,360 --> 00:04:22,350
je jasné, že seznam byl již řazeno, protože jsme neměli zaměnit nic.

90
00:04:22,350 --> 00:04:24,160
Takže jsme rozhodně nemusíme řadit znovu.

91
00:04:24,160 --> 00:04:27,960
>> Možná byste mohli inicializovat vlajky proměnnou s názvem "není seřazena" na

92
00:04:27,960 --> 00:04:30,990
false a změnit jej na hodnotu true, pokud máte vyměnit jakékoli prvky na

93
00:04:30,990 --> 00:04:32,290
jedna iterace přes pole.

94
00:04:32,290 --> 00:04:35,350
Nebo podobně, aby se čítač počítat, kolik swapy uděláte

95
00:04:35,350 --> 00:04:37,040
na dané iteraci.

96
00:04:37,040 --> 00:04:40,040
Na konci iterace, pokud nebyla vyměnit některý z prvků,

97
00:04:40,040 --> 00:04:41,780
víte, seznam je již seřazena a máte hotovo.

98
00:04:41,780 --> 00:04:44,090
Bubble Sort, stejně jako ostatní metody řazení, může být

99
00:04:44,090 --> 00:04:46,960
vylepšený pracovat pro všechny prvky, které mají uspořádání metody.

100
00:04:46,960 --> 00:04:50,610
>> To je vzhledem k tomu, dva prvky máte způsob, jak říct, pokud první

101
00:04:50,610 --> 00:04:53,770
je větší než, roven nebo menší než druhé.

102
00:04:53,770 --> 00:04:56,870
Například byste mohli řadit písmena abecedy vyslovením

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

104
00:05:00,520 --> 00:05:03,830
Nebo byste mohli řadit dny v týdnu, kdy je neděle méně do pondělí

105
00:05:03,830 --> 00:05:05,110
která je menší než úterý.

106
00:05:05,110 --> 00:05:09,630
>> Bubble Sort není v žádném případě velmi efektivní, nebo rychle třídění algoritmus.

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

108
00:05:12,370 --> 00:05:14,810
protože budete muset provést n iterací pomocí seznamu

109
00:05:14,810 --> 00:05:18,430
kontrolu všech n prvků každé pass-through, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
To běží čas znamená, že počet prvků jste třídění zvýšení,

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

112
00:05:24,330 --> 00:05:27,330
>> Ale pokud účinnost není velkým problémem vašeho programu

113
00:05:27,330 --> 00:05:29,550
nebo pokud jste jen řazení malý počet prvků,

114
00:05:29,550 --> 00:05:31,660
můžete najít Bubble Sort užitečné, protože

115
00:05:31,660 --> 00:05:33,360
je to jedna z nejjednodušších algoritmů třídění pochopit

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

117
00:05:34,250 --> 00:05:37,270
Je to také skvělý způsob, jak získat zkušenosti s překládáním teoretické

118
00:05:37,270 --> 00:05:40,220
algoritmus do skutečného fungování kódu.

119
00:05:40,220 --> 00:05:43,000
No, to je Bubble Sort pro vás. Díky za sledování.

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