1
00:00:00,000 --> 00:00:03,360
>> [Muzikos grojimo]

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

3
00:00:04,522 --> 00:00:06,730
Doug LLOYD: Gerai, taip
burbulas rūšiuoti yra algoritmas

4
00:00:06,730 --> 00:00:08,730
galite naudoti norėdami rūšiuoti iš elementų rinkinį.

5
00:00:08,730 --> 00:00:10,850
Paimkime, kaip ji veikia išvaizdą.

6
00:00:10,850 --> 00:00:13,240
>> Taigi pagrindinė idėja
burbulas rūšiuoti tai.

7
00:00:13,240 --> 00:00:17,340
Mes paprastai nori judėti didesnis
vertinami elementai paprastai į dešinę

8
00:00:17,340 --> 00:00:20,340
ir nuleiskite vertinami elementų, kuriais paprastai
į kairę, kaip galima būtų tikėtis.

9
00:00:20,340 --> 00:00:23,256
Mes norime, kad mažesnės dalykai turi būti ne
pradžia, ir aukštesni dalykai

10
00:00:23,256 --> 00:00:24,970
būti pabaigoje.

11
00:00:24,970 --> 00:00:26,130
>> Kaip mes tai darome?

12
00:00:26,130 --> 00:00:28,040
Na Pseudocode kodas,
galima sakyti, tegul

13
00:00:28,040 --> 00:00:30,320
nustatyti apsikeitimo skaitiklį į ne nulinės vertės.

14
00:00:30,320 --> 00:00:32,570
Pamatysime, kodėl mes galime padaryti, kad per sekundę.

15
00:00:32,570 --> 00:00:36,090
Ir tada mes pakartoti taip
procesas, kol apsikeitimo skaitiklis yra 0,

16
00:00:36,090 --> 00:00:39,910
arba tol, kol mes nedarome apsikeitimo ne visiems.

17
00:00:39,910 --> 00:00:43,170
>> Atstatyti apsikeitimo skaitiklį į
0, jei tai ne jau 0.

18
00:00:43,170 --> 00:00:46,420
Tada pažvelgti kas
greta elementų pora.

19
00:00:46,420 --> 00:00:49,550
Jei šie du elementai yra
ne tam, apsikeitimo juos,

20
00:00:49,550 --> 00:00:51,620
ir pridėti 1 iki apsikeitimo skaitiklis.

21
00:00:51,620 --> 00:00:53,870
Jei jūs galvojate apie
tai prieš jums vizualizuoti tai,

22
00:00:53,870 --> 00:00:57,471
pastebėsite, kad tai bus perkelti mažesnis
vertinami elementai į kairę

23
00:00:57,471 --> 00:01:00,720
ir didesnis vertinami elementus į dešinę,
efektyviai daryti tai, ką norime daryti,

24
00:01:00,720 --> 00:01:03,940
kuris yra perkelti šias grupes
iš elementų, tokiu būdu.

25
00:01:03,940 --> 00:01:07,035
Leiskite įsivaizduoti, kaip tai
gali atrodyti, naudodami mūsų masyvas

26
00:01:07,035 --> 00:01:10,504
kad mes naudojamas testas
iš šių algoritmų.

27
00:01:10,504 --> 00:01:13,420
Čia mes turime nerūšiuotas masyvo vėl,
visi iš elementų, nurodyta

28
00:01:13,420 --> 00:01:14,840
yra raudona spalva.

29
00:01:14,840 --> 00:01:17,970
Aš nukreipiau savo apsikeitimo skaitiklis
prie nulio vertės.

30
00:01:17,970 --> 00:01:20,610
Aš savavališkai pasirinko
neigiamas 1-- tai ne 0.

31
00:01:20,610 --> 00:01:23,840
Mes norime pakartoti šį procesą
iki apsikeitimo skaitiklis yra 0.

32
00:01:23,840 --> 00:01:26,540
Tai kodėl aš nustatyti savo apsikeitimo
prieštarauja tam tikru ne nulinės vertės,

33
00:01:26,540 --> 00:01:29,400
nes kitaip
apsikeitimo skaitiklis būtų 0.

34
00:01:29,400 --> 00:01:31,610
Mes net ne prasidės
procesas algoritmą.

35
00:01:31,610 --> 00:01:33,610
Taigi dar kartą, veiksmai are--
naujo apsikeitimo skaitiklis

36
00:01:33,610 --> 00:01:37,900
0, tada pažvelgti į kiekvieną šalia
pora, ir jei jie iš tam,

37
00:01:37,900 --> 00:01:40,514
apsikeitimo juos ir pridėti 1
į apsikeitimo skaitiklis.

38
00:01:40,514 --> 00:01:41,680
Taigi pradėkime šį procesą.

39
00:01:41,680 --> 00:01:44,430
Taigi pirmas dalykas, mes darome, yra
mes nustatome apsikeitimo skaitiklis 0,

40
00:01:44,430 --> 00:01:46,660
ir tada mes pradėti ieškoti
kiekvieno gretimo pora.

41
00:01:46,660 --> 00:01:49,140
>> Taigi mes pirmą kartą pradėti ieškoti 5 ir 2.

42
00:01:49,140 --> 00:01:52,410
Matome, kad jie yra iš
užsisakyti ir todėl mes apsikeitimo juos.

43
00:01:52,410 --> 00:01:53,830
Ir mes pridėti 1 iki apsikeitimo skaitiklis.

44
00:01:53,830 --> 00:01:57,860
Taigi dabar mūsų apsikeitimo skaitiklis yra 1,
ir 2 ir 5 buvo įjungtas.

45
00:01:57,860 --> 00:01:59,370
Dabar mes vėl pakartokite šį procesą.

46
00:01:59,370 --> 00:02:03,540
>> Pažvelgtume į kitą gretimos poros,
5 ir 1-- jie taip pat iš eilės,

47
00:02:03,540 --> 00:02:06,960
todėl mes apsikeitimo juos ir pridėti
1 apsikeitimo skaitiklis.

48
00:02:06,960 --> 00:02:08,900
Tada mes pažvelgti 5 ir 3.

49
00:02:08,900 --> 00:02:13,830
Jie iš eilės, todėl mes apsikeitimo
juos ir mes pridėsime 1 iki apsikeitimo skaitiklis.

50
00:02:13,830 --> 00:02:15,550
Tada mes pažvelgti 5 ir 6 d.

51
00:02:15,550 --> 00:02:18,630
Jie tam, kad mes ne iš tikrųjų
reikia sukeisti nieko šiuo metu.

52
00:02:18,630 --> 00:02:20,250
Tada mes pažvelgti 6 ir 4.

53
00:02:20,250 --> 00:02:24,920
Jie taip pat iš eilės, todėl mes apsikeitimo
juos ir mes pridėsime 1 iki apsikeitimo skaitiklis.

54
00:02:24,920 --> 00:02:26,230
>> Dabar pastebėti tai, kas atsitiko.

55
00:02:26,230 --> 00:02:29,514
Mes persikėlė 6 visą kelią iki galo.

56
00:02:29,514 --> 00:02:32,180
Taigi atrankos rūšiuoti, jei jūs
matyti, kad vaizdo, ką mes padarėme, buvo

57
00:02:32,180 --> 00:02:35,290
mes galų gale perstumiant
Mažiausi elementai pastato

58
00:02:35,290 --> 00:02:39,640
surūšiuoti masyvo ir iš esmės
kairės į dešinę, mažiausio iki didžiausių.

59
00:02:39,640 --> 00:02:43,200
Atsižvelgiant į burbulas rūšiuoti atveju, jei mes
po šio konkretaus algoritmo,

60
00:02:43,200 --> 00:02:46,720
mes iš tikrųjų ketiname būti pastato
surūšiuoti masyvas iš dešinės

61
00:02:46,720 --> 00:02:49,100
į kairę, didžiausiojo iki mažiausiojo.

62
00:02:49,100 --> 00:02:53,840
Mes efektyviai burbuliukais 6 d
didžiausia vertė, visą kelią iki galo.

63
00:02:53,840 --> 00:02:56,165
>> Ir taip dabar mes galime paskelbti
kad tai būtų rūšiuojamos,

64
00:02:56,165 --> 00:02:59,130
ir ateityje iterations--
išgyvena masyvo again--

65
00:02:59,130 --> 00:03:01,280
mes neturime apsvarstyti 6 nebėra.

66
00:03:01,280 --> 00:03:03,850
Mes turime tik mano
kad nerūšiuotos elementai

67
00:03:03,850 --> 00:03:06,299
kai mes ieškome gretimų porų.

68
00:03:06,299 --> 00:03:08,340
Taigi, mes turime baigė vieną
pro burbulas rūšiuoti.

69
00:03:08,340 --> 00:03:11,941
Taigi dabar mes einame atgal į klausimą,
kartokite tol, kol apsikeitimo skaitiklis yra 0.

70
00:03:11,941 --> 00:03:13,690
Na apsikeitimo skaitliukas
yra 4, todėl mes ketiname

71
00:03:13,690 --> 00:03:15,410
išlaikyti vėl kartoti šį procesą.

72
00:03:15,410 --> 00:03:19,180
>> Mes ketiname iš naujo apsikeitimo skaitiklis
0, ir ieškoti kiekvienos gretimos poros.

73
00:03:19,180 --> 00:03:21,890
Taigi, mes pradėti su 2 ir 1-- jie
iš eilės, todėl mes apsikeitimo juos

74
00:03:21,890 --> 00:03:23,620
ir mes pridėsime 1 iki apsikeitimo skaitiklis.

75
00:03:23,620 --> 00:03:25,490
2 ir 3, jie tam.

76
00:03:25,490 --> 00:03:27,060
Mums nereikia nieko daryti.

77
00:03:27,060 --> 00:03:28,420
3 ir 5 yra tam, kad.

78
00:03:28,420 --> 00:03:30,150
Mums nereikia nieko ten daryti.

79
00:03:30,150 --> 00:03:32,515
>> 5 ir 4, jie yra iš
iš eilės, ir todėl mes

80
00:03:32,515 --> 00:03:35,130
reikia sukeisti juos ir pridėti
1 apsikeitimo skaitiklis.

81
00:03:35,130 --> 00:03:38,880
Ir dabar mes persikėlė 5,
Kitas didžiausias elementas,

82
00:03:38,880 --> 00:03:40,920
į nerūšiuotųomis porcija pabaigoje.

83
00:03:40,920 --> 00:03:44,360
Taigi dabar mes galime skambinti, kad
dalis surūšiuoti porcijoje.

84
00:03:44,360 --> 00:03:47,180
>> Dabar jūs ieškote ne
ekranas ir tikriausiai galite pasakyti,

85
00:03:47,180 --> 00:03:50,130
kaip aš galiu, kad masyvo
yra rūšiuojami dabar.

86
00:03:50,130 --> 00:03:51,820
Bet mes negalime įrodyti, kad dar.

87
00:03:51,820 --> 00:03:54,359
Neturime garantiją
kad jis rūšiuojami.

88
00:03:54,359 --> 00:03:56,900
Bet tai kur apsikeitimo
skaitliukas ketina ateiti į žaidimą.

89
00:03:56,900 --> 00:03:59,060
>> Taigi mes baigė perdavimo.

90
00:03:59,060 --> 00:04:00,357
Apsikeitimo skaitiklis yra 2.

91
00:04:00,357 --> 00:04:02,190
Taigi mes ketiname pakartoti
vėl šis procesas,

92
00:04:02,190 --> 00:04:04,290
kartokite tol, kol apsikeitimo skaitiklis yra 0.

93
00:04:04,290 --> 00:04:05,550
Atstatyti apsikeitimo skaitiklis 0.

94
00:04:05,550 --> 00:04:06,820
Taigi mes jį atstatyti.

95
00:04:06,820 --> 00:04:09,810
>> Dabar pažvelgti į kiekvieną greta pora.

96
00:04:09,810 --> 00:04:11,880
Štai, kad 1 ir 2.

97
00:04:11,880 --> 00:04:13,590
2 ir 3 yra tam, kad.

98
00:04:13,590 --> 00:04:15,010
3 ir 4, yra tam, kad.

99
00:04:15,010 --> 00:04:19,250
Taigi šiuo metu, pastebėsite, mes baigtas
žiūri kiekvieną greta pora,

100
00:04:19,250 --> 00:04:22,530
bet apsikeitimo skaitiklis yra vis dar 0.

101
00:04:22,530 --> 00:04:25,520
>> Jei mes neturime pereiti
bet elementai, tada jie

102
00:04:25,520 --> 00:04:28,340
turi būti tam, kurį
dorybė šio proceso dalis.

103
00:04:28,340 --> 00:04:32,000
Ir taip AN rūšių efektyvumas,
kad mes kompiuterių mokslininkai myliu,

104
00:04:32,000 --> 00:04:35,560
yra dabar galime paskelbti
visas masyvas turi

105
00:04:35,560 --> 00:04:38,160
būti rūšiuojamos, nes mes ne
turi apsikeitimo jokių elementų.

106
00:04:38,160 --> 00:04:40,380
Tai gana gražus.

107
00:04:40,380 --> 00:04:43,260
>> Taigi, kas blogiausiu atveju
scenarijus su burbulas rūšiuoti?

108
00:04:43,260 --> 00:04:46,240
Blogiausiu atveju masyvas yra
į visiškai atvirkštine tvarka,

109
00:04:46,240 --> 00:04:49,870
ir todėl mes turime kiekvienas burbulas
didžiųjų elementų visi

110
00:04:49,870 --> 00:04:51,780
būdas visoje masyvo.

111
00:04:51,780 --> 00:04:55,350
Ir mes iš tikrųjų taip pat turi
burbuliukų visi mažų elementų atgal

112
00:04:55,350 --> 00:04:57,050
visą kelią visoje masyvo, taip pat.

113
00:04:57,050 --> 00:05:01,950
Taigi, kiekvienas iš n elementų turi judėti
visoje visų kitų n elementų.

114
00:05:01,950 --> 00:05:04,102
Taigi, kad blogiausiu atveju.

115
00:05:04,102 --> 00:05:05,810
Geriausiu atveju
scenarijus, nors tai

116
00:05:05,810 --> 00:05:07,880
šiek tiek skiriasi nuo atrankos rūšiuoti.

117
00:05:07,880 --> 00:05:10,040
Masyvas yra jau
rūšiuojamos, kai mes einame.

118
00:05:10,040 --> 00:05:12,550
Neturime padaryti bet
apsikeitimo pirmame praeiti.

119
00:05:12,550 --> 00:05:14,940
Taigi, mes galime pažvelgti
ne mažiau elementų, tiesa?

120
00:05:14,940 --> 00:05:18,580
Neturime pakartoti
apdoroti keletą kartų per.

121
00:05:18,580 --> 00:05:19,540
>> Taigi, ką tai reiškia?

122
00:05:19,540 --> 00:05:22,390
Taigi, kas yra blogiausias scenarijus
Kramtomoji rūšiuoti, ir kas

123
00:05:22,390 --> 00:05:25,330
Geriausiu atveju scenarijus burbulas rūšiuoti?

124
00:05:25,330 --> 00:05:27,770
Ar galite atspėti, tai?

125
00:05:27,770 --> 00:05:32,420
Blogiausiu atveju jūs turite pakartoti
visose n elementų n kartų.

126
00:05:32,420 --> 00:05:34,220
Taigi blogiausiu atveju yra N kvadratu.

127
00:05:34,220 --> 00:05:36,550
>> Jei masyvas yra puikiai
Rūšiuoti nors, jūs tik

128
00:05:36,550 --> 00:05:38,580
pažvelgti į kiekvieną
Vieną kartą elementų.

129
00:05:38,580 --> 00:05:42,670
Ir jei apsikeitimo skaitiklis yra vis dar 0,
galite pasakyti, kad tai masyvas surūšiuotas.

130
00:05:42,670 --> 00:05:45,780
Ir taip geriausiu atveju, tai yra
tikrai geriau nei atrankos

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

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

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

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