1
00:00:00,000 --> 00:00:03,360
>> [Prehrávanie hudby]

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

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Dobre, tak
bublina triedenie je algoritmus

4
00:00:06,730 --> 00:00:08,730
môžete použiť radiť sadu prvkov.

5
00:00:08,730 --> 00:00:10,850
Poďme sa pozrieť, ako to funguje.

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

7
00:00:13,240 --> 00:00:17,340
Všeobecne chceme presunúť vyššie
cenené prvky, zvyčajne na pravej strane,

8
00:00:17,340 --> 00:00:20,340
a nižšej hodnote prvky všeobecne
doľava, ako by sme očakávali.

9
00:00:20,340 --> 00:00:23,256
Chceme, aby spodná veci boli v
začiatok, a vyššie veci

10
00:00:23,256 --> 00:00:24,970
byť na konci.

11
00:00:24,970 --> 00:00:26,130
>> Ako to robíme?

12
00:00:26,130 --> 00:00:28,040
No v pseudokódu kódu,
Dalo by sa povedať, poďme

13
00:00:28,040 --> 00:00:30,320
nastaviť počítadlo odkladacie nenulovú hodnotu.

14
00:00:30,320 --> 00:00:32,570
Uvidíme, prečo to robíme, že v sekunde.

15
00:00:32,570 --> 00:00:36,090
A potom sme zopakovať nasledujúce
Proces, keď čítač swap je 0,

16
00:00:36,090 --> 00:00:39,910
alebo kým nerobíme swapy vôbec.

17
00:00:39,910 --> 00:00:43,170
>> Vynulujte počítadlo odkladacia
0, ak to nie je už 0.

18
00:00:43,170 --> 00:00:46,420
Potom sa pozrite na každý
priľahlé dvojice prvkov.

19
00:00:46,420 --> 00:00:49,550
Ak sa tieto dva prvky sú
nie je v poriadku, je vymeniť,

20
00:00:49,550 --> 00:00:51,620
a pridať 1 k pultu swapu.

21
00:00:51,620 --> 00:00:53,870
Ak uvažujete o
to skôr, ako ho predstaviť,

22
00:00:53,870 --> 00:00:57,471
Všimnite si, že to bude pohybovať nižšia
oceňujú prvky vľavo

23
00:00:57,471 --> 00:01:00,720
a vyššie oceňujú prvky vpravo,
účinne robiť to, čo chceme robiť,

24
00:01:00,720 --> 00:01:03,940
čo je presunúť tieto skupiny
prvkov týmto spôsobom.

25
00:01:03,940 --> 00:01:07,035
Poďme si predstaviť, ako to
môže vyzerať pomocou našej ponuku

26
00:01:07,035 --> 00:01:10,504
že používa na testovanie
out týchto algoritmov.

27
00:01:10,504 --> 00:01:13,420
Máme tu k netriedené poľa znova,
označené všetky prvky

28
00:01:13,420 --> 00:01:14,840
je v červenej farbe.

29
00:01:14,840 --> 00:01:17,970
A obrátil som počítadlo odkladacia
na nenulovú hodnotu.

30
00:01:17,970 --> 00:01:20,610
Aj ľubovoľne si vybral
Negatívny 1-- to nie je 0.

31
00:01:20,610 --> 00:01:23,840
Chceme, aby tento proces opakovať
do pultu odkladacieho 0.

32
00:01:23,840 --> 00:01:26,540
To je dôvod, prečo som nastaviť svoj swapu
v rozpore s nejakou nenulovú hodnotu,

33
00:01:26,540 --> 00:01:29,400
pretože inak
odkladací pult by byť 0.

34
00:01:29,400 --> 00:01:31,610
Nemali by sme ani začne plynúť
Spôsob podľa tohto algoritmu.

35
00:01:31,610 --> 00:01:33,610
Takže znova, kroky are--
vynulovať počítadlo odkladacia

36
00:01:33,610 --> 00:01:37,900
na 0, potom sa pozrite na každom priľahlý
pair, a či sú mimo prevádzky,

37
00:01:37,900 --> 00:01:40,514
je vymeniť, a pridať 1
k pultu swapu.

38
00:01:40,514 --> 00:01:41,680
Takže poďme začať tento proces.

39
00:01:41,680 --> 00:01:44,430
Takže prvá vec, ktorú robíme, je
nastavíme čítač odkladacie na 0,

40
00:01:44,430 --> 00:01:46,660
a potom začneme hľadať
v každej susednej dvojice.

41
00:01:46,660 --> 00:01:49,140
>> Tak sme najprv začať uvažovať o 5 a 2.

42
00:01:49,140 --> 00:01:52,410
Vidíme, že sú mimo
objednať a tak sme ich vymeniť.

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

44
00:01:53,830 --> 00:01:57,860
Takže teraz náš čítač swap je 1,
a 2 a 5 boli prepnutý.

45
00:01:57,860 --> 00:01:59,370
Teraz sme opäť proces opakovať.

46
00:01:59,370 --> 00:02:03,540
>> Pozerali sme sa na ďalšiu susedné dvojice,
5 a 1-- sú tiež mimo prevádzku,

47
00:02:03,540 --> 00:02:06,960
tak sme ich vymeniť a pridať
1 k pultu swapu.

48
00:02:06,960 --> 00:02:08,900
Potom sa pozrieme na 5 a 3.

49
00:02:08,900 --> 00:02:13,830
Sú mimo prevádzky, takže sme vymeniť
je a pridáme 1 k pultu swapu.

50
00:02:13,830 --> 00:02:15,550
Potom sa pozrieme na 5 a 6.

51
00:02:15,550 --> 00:02:18,630
Sú v poriadku, takže my vlastne
je potrebné vymeniť čokoľvek tentoraz.

52
00:02:18,630 --> 00:02:20,250
Potom sa pozrieme na 6 a 4.

53
00:02:20,250 --> 00:02:24,920
Sú tiež mimo prevádzky, takže sme vymeniť
je a pridáme 1 k pultu swapu.

54
00:02:24,920 --> 00:02:26,230
>> Teraz si všimnúť, čo sa stalo.

55
00:02:26,230 --> 00:02:29,514
Presunuli sme 6 celú cestu až do konca.

56
00:02:29,514 --> 00:02:32,180
Takže vo výbere druhu, ak ste
vidieť, že video, čo sme urobili, bolo

57
00:02:32,180 --> 00:02:35,290
sme skončili pohybom
Najmenší prvky v budove

58
00:02:35,290 --> 00:02:39,640
roztriedený poľa v podstate od
zľava doprava, najmenší k najväčšej.

59
00:02:39,640 --> 00:02:43,200
V prípade bublina druhu, keď sme
po tejto konkrétnej algoritmus,

60
00:02:43,200 --> 00:02:46,720
my vlastne bude stavať
roztriedený poľa sprava

61
00:02:46,720 --> 00:02:49,100
doľava, najväčší po najmenšie.

62
00:02:49,100 --> 00:02:53,840
Máme skutočne bublala 6,
Najväčšia hodnota, až do konca.

63
00:02:53,840 --> 00:02:56,165
>> A tak teraz môžeme vyhlásiť,
že je triedený,

64
00:02:56,165 --> 00:02:59,130
a v budúcnosti iterations--
prechádza pole again--

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

66
00:03:01,280 --> 00:03:03,850
Máme len zvážiť
netriedeného prvky

67
00:03:03,850 --> 00:03:06,299
keď sa pozeráme na susedných párov.

68
00:03:06,299 --> 00:03:08,340
Takže sme skončili jeden
prejsť bublina druhu.

69
00:03:08,340 --> 00:03:11,941
Takže teraz sa vrátime k otázke,
opakujte, kým počítadlo swap je 0.

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

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

72
00:03:15,410 --> 00:03:19,180
>> Chystáme sa vynulovať počítadlo odkladací
na 0, a pozrieť sa na každým susedným párom.

73
00:03:19,180 --> 00:03:21,890
Takže začneme s 2 a 1-- sú
mimo prevádzky, takže sme ich vymeniť

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

75
00:03:23,620 --> 00:03:25,490
2 a 3, sú v poriadku.

76
00:03:25,490 --> 00:03:27,060
Nepotrebujeme nič robiť.

77
00:03:27,060 --> 00:03:28,420
3 a 5 sú v poriadku.

78
00:03:28,420 --> 00:03:30,150
Nepotrebujeme nič robiť tam.

79
00:03:30,150 --> 00:03:32,515
>> 5 a 4, sú mimo
prevádzku, a tak sme

80
00:03:32,515 --> 00:03:35,130
je potrebné ich vymeniť a pridať
1 k pultu swapu.

81
00:03:35,130 --> 00:03:38,880
A teraz sme sa presťahovali 5,
Budúci najväčšie prvok,

82
00:03:38,880 --> 00:03:40,920
na koniec netriedeného časti.

83
00:03:40,920 --> 00:03:44,360
Takže môžeme teraz hovoriť, že
časť usporiadané časti.

84
00:03:44,360 --> 00:03:47,180
>> Teraz pri pohľade na
obrazovky a pravdepodobne môže povedať,

85
00:03:47,180 --> 00:03:50,130
ako môžem, aby polia
Je radené práve teraz.

86
00:03:50,130 --> 00:03:51,820
Ale nemôžeme dokázať, že doteraz.

87
00:03:51,820 --> 00:03:54,359
Nemáme záruku
že je to triediť.

88
00:03:54,359 --> 00:03:56,900
Ale to je miesto, kde swap
Počítadlo to príde do hry.

89
00:03:56,900 --> 00:03:59,060
>> Preto sme dokončili a nahráva.

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 opakovať
sa tento proces,

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

93
00:04:04,290 --> 00:04:05,550
Vynulujte počítadlo odkladacie 0.

94
00:04:05,550 --> 00:04:06,820
Takže my ho resetovať.

95
00:04:06,820 --> 00:04:09,810
>> Teraz sa pozrite na každým susednom párom.

96
00:04:09,810 --> 00:04:11,880
To je v poriadku, 1 a 2.

97
00:04:11,880 --> 00:04:13,590
2 a 3 sú v poriadku.

98
00:04:13,590 --> 00:04:15,010
3 a 4 sú v poriadku.

99
00:04:15,010 --> 00:04:19,250
Takže v tomto bode, Všimnite si, že sme dokončili
pri pohľadu na každej susednej 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
>> Ak nebudeme musieť prejsť
niektoré prvky, potom sa

102
00:04:25,520 --> 00:04:28,340
musí byť v poriadku tým, že
Na základe tohto procesu.

103
00:04:28,340 --> 00:04:32,000
A tak účinnosťou druhov,
Že sme počítačoví odborníci milujeme,

104
00:04:32,000 --> 00:04:35,560
je teraz môžeme vyhlásiť,
celé pole musí

105
00:04:35,560 --> 00:04:38,160
triedené, pretože sme nemali
musieť vymeniť akékoľvek prvky.

106
00:04:38,160 --> 00:04:40,380
To je celkom pekné.

107
00:04:40,380 --> 00:04:43,260
>> Takže to, čo je najhorší prípad
Scenár s bublinkové radenia?

108
00:04:43,260 --> 00:04:46,240
V najhoršom prípade je pole
v úplne opačnom poradí,

109
00:04:46,240 --> 00:04:49,870
a preto musíme bublina každý
veľkých prvkov all

110
00:04:49,870 --> 00:04:51,780
cestu cez pole.

111
00:04:51,780 --> 00:04:55,350
A my efektívne musieť tiež
bublina všetkých malých prvkov späť

112
00:04:55,350 --> 00:04:57,050
celú cestu cez pole, tiež.

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

114
00:05:01,950 --> 00:05:04,102
Tak to je ten najhorší možný scenár.

115
00:05:04,102 --> 00:05:05,810
V najlepšom prípade
scenár aj keď, je to

116
00:05:05,810 --> 00:05:07,880
mierne líši od výberu druhu.

117
00:05:07,880 --> 00:05:10,040
Pole je už
radené keď ideme dovnútra.

118
00:05:10,040 --> 00:05:12,550
My nemusíme vykonávať žiadne
swapy na prvom prechode.

119
00:05:12,550 --> 00:05:14,940
Takže možno budeme musieť hľadať
na menej prvkov, nie?

120
00:05:14,940 --> 00:05:18,580
My nemusíme opakovať
spracovať niekoľkokrát viac než.

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

122
00:05:19,540 --> 00:05:22,390
Takže to, čo je najhorší možný scenár
k Bubble druhu, a to, čo je

123
00:05:22,390 --> 00:05:25,330
najlepší scenár pre bubble druhu?

124
00:05:25,330 --> 00:05:27,770
Vedeli ste, že toto?

125
00:05:27,770 --> 00:05:32,420
V najhoršom prípade musíte iterovat
naprieč všetkými n elementy n-krát.

126
00:05:32,420 --> 00:05:34,220
Takže najhorší prípad je n na druhú.

127
00:05:34,220 --> 00:05:36,550
>> V prípade, že pole je dokonale
triedených aj keď, len vy

128
00:05:36,550 --> 00:05:38,580
sa pozrieť na seba
prvkov raz.

129
00:05:38,580 --> 00:05:42,670
A v prípade, že počítadlo swap je stále 0,
môžete povedať toto pole je triedený.

130
00:05:42,670 --> 00:05:45,780
A tak v najlepšom prípade sa jedná
vlastne lepšie ako výber

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

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

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

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