1
00:00:00,000 --> 00:00:03,360
>> [Přehrávání hudby]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Dobře, tak
bublina třídění je algoritmus

4
00:00:06,730 --> 00:00:08,730
můžete použít řadit sadu prvků.

5
00:00:08,730 --> 00:00:10,850
Pojďme se podívat, jak to funguje.

6
00:00:10,850 --> 00:00:13,240
>> Takže základní myšlenka
bubble sort je to.

7
00:00:13,240 --> 00:00:17,340
Obecně chceme přesunout vyšší
ceněné prvky, obvykle na pravé straně,

8
00:00:17,340 --> 00:00:20,340
a nižší hodnotě prvky obecně
doleva, jak bychom očekávali.

9
00:00:20,340 --> 00:00:23,256
Chceme, aby spodní věci byly v
začátek, a vyšší věci

10
00:00:23,256 --> 00:00:24,970
být na konci.

11
00:00:24,970 --> 00:00:26,130
>> Jak to děláme?

12
00:00:26,130 --> 00:00:28,040
No v pseudokódu kódu,
Dalo by se říci, pojďme

13
00:00:28,040 --> 00:00:30,320
nastavit počítadlo odkládací nenulovou hodnotu.

14
00:00:30,320 --> 00:00:32,570
Uvidíme, proč to děláme, že ve vteřině.

15
00:00:32,570 --> 00:00:36,090
A pak jsme zopakovat následující
Proces, když čítač swap je 0,

16
00:00:36,090 --> 00:00:39,910
nebo dokud neděláme swapy vůbec.

17
00:00:39,910 --> 00:00:43,170
>> Vynulujte počítadlo odkládací
0, pokud to není už 0.

18
00:00:43,170 --> 00:00:46,420
Pak se podívejte na každý
přilehlé dvojice prvků.

19
00:00:46,420 --> 00:00:49,550
Pokud se tyto dva prvky jsou
není v pořádku, je vyměnit,

20
00:00:49,550 --> 00:00:51,620
a přidat 1 k pultu swapu.

21
00:00:51,620 --> 00:00:53,870
Pokud uvažujete o
to dříve, než ho představit,

22
00:00:53,870 --> 00:00:57,471
Všimněte si, že to bude pohybovat nižší
oceňují prvky vlevo

23
00:00:57,471 --> 00:01:00,720
a vyšší oceňují prvky vpravo,
účinně dělat to, co chceme dělat,

24
00:01:00,720 --> 00:01:03,940
což je přesunout tyto skupiny
prvků tímto způsobem.

25
00:01:03,940 --> 00:01:07,035
Pojďme si představit, jak to
může vypadat pomocí naší nabídku

26
00:01:07,035 --> 00:01:10,504
že používá k testování
out těchto algoritmů.

27
00:01:10,504 --> 00:01:13,420
Máme zde k netříděné pole znovu,
označeny všechny prvky

28
00:01:13,420 --> 00:01:14,840
je v červené barvě.

29
00:01:14,840 --> 00:01:17,970
A obrátil jsem počítadlo odkládací
na nenulovou hodnotu.

30
00:01:17,970 --> 00:01:20,610
I libovolně si vybral
Negativní 1-- to není 0.

31
00:01:20,610 --> 00:01:23,840
Chceme, aby tento proces opakovat
do pultu odkládacího 0.

32
00:01:23,840 --> 00:01:26,540
To je důvod, proč jsem nastavit svůj swapu
v rozporu s nějakou nenulovou hodnotu,

33
00:01:26,540 --> 00:01:29,400
protože jinak
odkládací pult by být 0.

34
00:01:29,400 --> 00:01:31,610
Neměli bychom ani začne běžet
Způsob podle tohoto algoritmu.

35
00:01:31,610 --> 00:01:33,610
Takže znovu, kroky are--
vynulovat počítadlo odkládací

36
00:01:33,610 --> 00:01:37,900
na 0, pak se podívejte na každém přilehlý
pair, a jestli jsou mimo provoz,

37
00:01:37,900 --> 00:01:40,514
je vyměnit, a přidat 1
k pultu swapu.

38
00:01:40,514 --> 00:01:41,680
Takže pojďme začít tento proces.

39
00:01:41,680 --> 00:01:44,430
Takže první věc, kterou děláme, je
nastavíme čítač odkládací na 0,

40
00:01:44,430 --> 00:01:46,660
a pak začneme hledat
v každé sousední dvojice.

41
00:01:46,660 --> 00:01:49,140
>> Tak jsme nejprve začít uvažovat o 5 a 2.

42
00:01:49,140 --> 00:01:52,410
Vidíme, že jsou mimo
objednat a tak jsme je vyměnit.

43
00:01:52,410 --> 00:01:53,830
A přidáme 1 k pultu swapu.

44
00:01:53,830 --> 00:01:57,860
Takže teď náš čítač swap je 1,
a 2 a 5 byly přepnut.

45
00:01:57,860 --> 00:01:59,370
Nyní jsme opět proces opakovat.

46
00:01:59,370 --> 00:02:03,540
>> Dívali jsme se na další sousední dvojice,
5 a 1-- jsou také mimo provoz,

47
00:02:03,540 --> 00:02:06,960
tak jsme je vyměnit a přidat
1 k pultu swapu.

48
00:02:06,960 --> 00:02:08,900
Pak se podíváme na 5 a 3.

49
00:02:08,900 --> 00:02:13,830
Jsou mimo provoz, takže jsme vyměnit
je a přidáme 1 k pultu swapu.

50
00:02:13,830 --> 00:02:15,550
Pak se podíváme na 5 a 6.

51
00:02:15,550 --> 00:02:18,630
Jsou v pořádku, takže my vlastně
je třeba vyměnit cokoliv tentokrát.

52
00:02:18,630 --> 00:02:20,250
Pak se podíváme na 6 a 4.

53
00:02:20,250 --> 00:02:24,920
Jsou také mimo provoz, takže jsme vyměnit
je a přidáme 1 k pultu swapu.

54
00:02:24,920 --> 00:02:26,230
>> Teď si všimnout, co se stalo.

55
00:02:26,230 --> 00:02:29,514
Přesunuli jsme 6 celou cestu až do konce.

56
00:02:29,514 --> 00:02:32,180
Takže ve výběru druhu, pokud jste
vidět, že video, co jsme udělali, bylo

57
00:02:32,180 --> 00:02:35,290
jsme skončili pohybem
Nejmenší prvky v budově

58
00:02:35,290 --> 00:02:39,640
roztříděný pole v podstatě od
zleva doprava, nejmenší k největší.

59
00:02:39,640 --> 00:02:43,200
V případě bublina druhu, když jsme
po této konkrétní algoritmus,

60
00:02:43,200 --> 00:02:46,720
my vlastně bude stavět
roztříděný pole zprava

61
00:02:46,720 --> 00:02:49,100
doleva, největší po nejmenší.

62
00:02:49,100 --> 00:02:53,840
Máme skutečně bublala 6,
Největší hodnota, až do konce.

63
00:02:53,840 --> 00:02:56,165
>> A tak nyní můžeme prohlásit,
že je tříděn,

64
00:02:56,165 --> 00:02:59,130
a v budoucnu iterations--
prochází pole again--

65
00:02:59,130 --> 00:03:01,280
nemusíme uvažovat už 6.

66
00:03:01,280 --> 00:03:03,850
Máme jen zvážit
netříděného prvky

67
00:03:03,850 --> 00:03:06,299
když se díváme na sousedních párů.

68
00:03:06,299 --> 00:03:08,340
Takže jsme skončili jeden
projít bublina druhu.

69
00:03:08,340 --> 00:03:11,941
Takže teď se vrátíme k otázce,
opakujte, dokud počítadlo swap je 0.

70
00:03:11,941 --> 00:03:13,690
No counter swapu
je 4, takže jdeme

71
00:03:13,690 --> 00:03:15,410
aby znovu opakovat tento proces.

72
00:03:15,410 --> 00:03:19,180
>> Chystáme se vynulovat počítadlo odkládací
na 0, a podívat se na každým sousedním párem.

73
00:03:19,180 --> 00:03:21,890
Takže začneme s 2 a 1-- jsou
mimo provoz, takže jsme je vyměnit

74
00:03:21,890 --> 00:03:23,620
a přidáme 1 k pultu swapu.

75
00:03:23,620 --> 00:03:25,490
2 a 3, jsou v pořádku.

76
00:03:25,490 --> 00:03:27,060
Nepotřebujeme nic dělat.

77
00:03:27,060 --> 00:03:28,420
3 a 5 jsou v pořádku.

78
00:03:28,420 --> 00:03:30,150
Nepotřebujeme nic dělat tam.

79
00:03:30,150 --> 00:03:32,515
>> 5 a 4, jsou mimo
provoz, a tak jsme

80
00:03:32,515 --> 00:03:35,130
je třeba je vyměnit a přidat
1 k pultu swapu.

81
00:03:35,130 --> 00:03:38,880
A teď jsme se přestěhovali 5,
Příští největší prvek,

82
00:03:38,880 --> 00:03:40,920
na konec netříděného části.

83
00:03:40,920 --> 00:03:44,360
Takže můžeme teď říkat, že
část uspořádané části.

84
00:03:44,360 --> 00:03:47,180
>> Teď při pohledu na
obrazovky a pravděpodobně může říct,

85
00:03:47,180 --> 00:03:50,130
jak můžu, že pole
Je řazeny právě teď.

86
00:03:50,130 --> 00:03:51,820
Ale nemůžeme dokázat, že dosud.

87
00:03:51,820 --> 00:03:54,359
Nemáme záruku
že je to třídit.

88
00:03:54,359 --> 00:03:56,900
Ale to je místo, kde swap
Počítadlo to přijde do hry.

89
00:03:56,900 --> 00:03:59,060
>> Proto jsme dokončili a nahrává.

90
00:03:59,060 --> 00:04:00,357
Počítadlo swap je 2.

91
00:04:00,357 --> 00:04:02,190
Takže budeme opakovat
se tento proces,

92
00:04:02,190 --> 00:04:04,290
opakujte, dokud počítadlo swap je 0.

93
00:04:04,290 --> 00:04:05,550
Vynulujte počitadlo odkládací 0.

94
00:04:05,550 --> 00:04:06,820
Takže my jej resetovat.

95
00:04:06,820 --> 00:04:09,810
>> Nyní se podívejte na každým sousedním párem.

96
00:04:09,810 --> 00:04:11,880
To je v pořádku, 1 a 2.

97
00:04:11,880 --> 00:04:13,590
2 a 3 jsou v pořádku.

98
00:04:13,590 --> 00:04:15,010
3 a 4 jsou v pořádku.

99
00:04:15,010 --> 00:04:19,250
Takže v tomto bodě, Všimněte si, že jsme dokončili
při pohledu na každé sousední dvojice,

100
00:04:19,250 --> 00:04:22,530
ale počítadlo swap je stále 0.

101
00:04:22,530 --> 00:04:25,520
>> Pokud nebudeme muset přejít
některé prvky, pak se

102
00:04:25,520 --> 00:04:28,340
musí být v pořádku tím, že
Na základě tohoto procesu.

103
00:04:28,340 --> 00:04:32,000
A tak účinností druhů,
Že jsme počítačoví odborníci milujeme,

104
00:04:32,000 --> 00:04:35,560
je nyní můžeme prohlásit,
celé pole musí

105
00:04:35,560 --> 00:04:38,160
tříděny, protože jsme neměli
muset vyměnit jakékoli prvky.

106
00:04:38,160 --> 00:04:40,380
To je docela pěkné.

107
00:04:40,380 --> 00:04:43,260
>> Takže to, co je nejhorší případ
Scénář s bublinkové řazení?

108
00:04:43,260 --> 00:04:46,240
V nejhorším případě je pole
ve zcela opačném pořadí,

109
00:04:46,240 --> 00:04:49,870
a proto musíme bublina každý
velkých prvků all

110
00:04:49,870 --> 00:04:51,780
cestu přes pole.

111
00:04:51,780 --> 00:04:55,350
A my efektivně muset také
bublina všech malých prvků zpět

112
00:04:55,350 --> 00:04:57,050
celou cestu přes pole, také.

113
00:04:57,050 --> 00:05:01,950
Takže každý z n elementy se musí pohybovat
v rámci všech ostatních n elementy.

114
00:05:01,950 --> 00:05:04,102
Tak to je ten nejhorší možný scénář.

115
00:05:04,102 --> 00:05:05,810
V nejlepším případě
scénář i když, je to

116
00:05:05,810 --> 00:05:07,880
mírně liší od výběru druhu.

117
00:05:07,880 --> 00:05:10,040
Pole je již
řazeny když jdeme dovnitř.

118
00:05:10,040 --> 00:05:12,550
My nemusíme provádět žádné
swapy na prvním průchodu.

119
00:05:12,550 --> 00:05:14,940
Takže možná budeme muset hledat
na méně prvků, ne?

120
00:05:14,940 --> 00:05:18,580
My nemusíme opakovat
zpracovat několikrát více než.

121
00:05:18,580 --> 00:05:19,540
>> Takže co to znamená?

122
00:05:19,540 --> 00:05:22,390
Takže to, co je nejhorší možný scénář
k Bubble druhu, a to, co je

123
00:05:22,390 --> 00:05:25,330
nejlepší scénář pro bubble druhu?

124
00:05:25,330 --> 00:05:27,770
Věděli jste, že tohle?

125
00:05:27,770 --> 00:05:32,420
V nejhorším případě musíte iterovat
napříč všemi n elementy n-krát.

126
00:05:32,420 --> 00:05:34,220
Takže nejhorší případ je n na druhou.

127
00:05:34,220 --> 00:05:36,550
>> V případě, že pole je dokonale
tříděných i když, jen vy

128
00:05:36,550 --> 00:05:38,580
se podívat na sebe
prvků jednou.

129
00:05:38,580 --> 00:05:42,670
A v případě, že počítadlo swap je stále 0,
můžete říci toto pole je tříděn.

130
00:05:42,670 --> 00:05:45,780
A tak v nejlepším případě se jedná
vlastně lepší než výběr

131
00:05:45,780 --> 00:05:49,230
sort-- to je omega n.

132
00:05:49,230 --> 00:05:50,270
>> Jsem Doug Lloyd.

133
00:05:50,270 --> 00:05:52,140
To je CS50.

134
00:05:52,140 --> 00:05:54,382