1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [BUBBLE RŪŠIUOTI]

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP Harvardo universiteto]

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

4
00:00:08,000 --> 00:00:11,730
Burbulas Rūšiuoti rūšiavimo algoritmą pavyzdys -

5
00:00:11,730 --> 00:00:14,460
kad yra elementų rinkinys rūšiavimo tvarka

6
00:00:14,460 --> 00:00:15,840
didėjimo arba mažėjimo tvarka.

7
00:00:15,840 --> 00:00:18,710
Pavyzdžiui, jei norite rūšiuoti masyvo, sudarytas iš skaičių

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], teisingas įgyvendinimas Bubble Rūšiuoti sugrįš

9
00:00:23,060 --> 00:00:26,260
surūšiuoti masyvas [2, 3, 5, 9] didėjimo tvarka.

10
00:00:26,260 --> 00:00:28,850
Dabar, aš paaiškinti pseudocode, kaip algoritmas veikia.

11
00:00:28,850 --> 00:00:34,000
>> Tarkime, mes rūšiavimo 5 sveikųjų skaičių sąrašą 3, 2, 9, 6, 5.

12
00:00:34,000 --> 00:00:37,650
Algoritmas prasideda žiūri pirmaisiais dviem elementais, 3 ir 2,

13
00:00:37,650 --> 00:00:40,850
ir tikrinti, ar jie iš siekiant tarpusavyje susijusius.

14
00:00:40,850 --> 00:00:43,150
Jie - 3 yra didesnis kaip 2.

15
00:00:43,150 --> 00:00:45,190
Būti didėjančia tvarka, jie turėtų būti atvirkščiai.

16
00:00:45,190 --> 00:00:46,610
Taigi, mes apsikeitimo juos.

17
00:00:46,610 --> 00:00:49,760
Dabar sąrašas atrodo panašus į šį: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Be to, mes pažvelgti į antros ir trečios dalių, 3 ir 9.

19
00:00:52,450 --> 00:00:55,770
Jie teisinga tvarka, viena kitos atžvilgiu.

20
00:00:55,770 --> 00:00:58,800
Tai reiškia, kad 3 yra mažesnis kaip 9, algoritmas nėra apsikeitimo juos.

21
00:00:58,800 --> 00:01:01,900
Be to, mes tikimės, 9 ir 6. Jie ne iš eilės.

22
00:01:01,900 --> 00:01:04,260
>> Taigi, mes turime apsikeitimo juos, nes 9 yra didesnis kaip 6.

23
00:01:04,260 --> 00:01:08,840
Galiausiai, mes pažvelgti į pastaruosius du sveikieji skaičiai, 9 ir 5.

24
00:01:08,840 --> 00:01:10,850
Jie ne iš eilės, todėl jie turi būti sukeistas.

25
00:01:10,850 --> 00:01:13,360
Po pirmojo visiškai patenka per sąrašą,

26
00:01:13,360 --> 00:01:17,140
atrodo panašus į šį: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Nėra blogai. Tai beveik surūšiuoti.

28
00:01:19,690 --> 00:01:22,450
Bet mes turime paleisti per sąrašą, vėl jį gauti visiškai rūšiuojami.

29
00:01:22,450 --> 00:01:29,250
Du yra mažesnis nei 3, todėl mes negalime apsikeitimo juos.

30
00:01:29,250 --> 00:01:31,700
>> Trys yra mažiau nei 6, todėl mes negalime apsikeitimo juos.

31
00:01:31,700 --> 00:01:35,500
Šeši yra didesnis nei 5. Mes pavertė.

32
00:01:35,500 --> 00:01:38,460
Six "yra mažesnis kaip 9. Mes neturime apsikeitimo.

33
00:01:38,460 --> 00:01:42,170
Po antrojo skrendant per, atrodo taip: [2, 3, 5, 6, 9]. Tobula.

34
00:01:42,170 --> 00:01:44,680
Dabar galime rašyti į pseudocode.

35
00:01:44,680 --> 00:01:48,450
Iš esmės, kiekvieno sąrašo elemento, mes turime pažvelgti į ją

36
00:01:48,450 --> 00:01:50,060
elementas tiesiogiai į savo teisę.

37
00:01:50,060 --> 00:01:53,420
Jei jie yra ne iš eilės lyginant su kiekviena kita - tai yra, jei kairėje elementas

38
00:01:53,420 --> 00:01:56,810
yra didesnis, nei dešinėje pusėje - turėtume sukeisti du elementus.

39
00:01:56,810 --> 00:02:01,270
>> Mes tai darome, kiekvienas sąrašo elementas, ir mes padarėme vieną pro.

40
00:02:01,270 --> 00:02:05,160
Dabar mes tiesiog daryti pass-through pakankamai kartų, siekiant užtikrinti, sąrašą

41
00:02:05,160 --> 00:02:06,480
yra visiškai ir tinkamai surūšiuoti.

42
00:02:06,480 --> 00:02:08,889
Bet kiek kartų mes turime praeiti pro sąraše

43
00:02:08,889 --> 00:02:10,400
garantuoti, kad mes padarėme?

44
00:02:10,400 --> 00:02:14,730
Na, blogiausiu atveju scenarijus, jei mes turime visiškai atgal sąrašą.

45
00:02:14,730 --> 00:02:17,840
Tada ji užima Pass-throughs lygus skaičius

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

47
00:02:19,730 --> 00:02:24,720
Jei tai nėra prasmės intuityviai, manau, paprastu atveju - sąrašas [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Ketina imtis 1 pass-through, rūšiuoti teisingai.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - blogiausiu atveju yra tai, kad su 3 elementus surūšiuoti atgal

50
00:02:33,060 --> 00:02:34,830
ji ketina imtis 2 iteracijų rūšiuoti.

51
00:02:34,830 --> 00:02:37,980
Po vienos iteracijos, [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Antra duoda surūšiuoti masyvas [1, 2, 3]

53
00:02:39,550 --> 00:02:43,350
Taigi jūs žinote, jūs niekada neturite eiti per masyvo, apskritai,

54
00:02:43,350 --> 00:02:46,790
daugiau nei n-1 kartų, kur n - masyvo elementų skaičius.

55
00:02:47,090 --> 00:02:50,470
Tai vadinama burbulas Rūšiuoti nes didžiausi elementai turi tendenciją "burbuliukų"

56
00:02:50,470 --> 00:02:51,950
gana greitai į dešinę.

57
00:02:51,950 --> 00:02:53,980
Tiesą sakant, šis algoritmas turi labai įdomią elgesį.

58
00:02:53,980 --> 00:02:57,410
>> Po m iteracijų per visą masyvą,

59
00:02:57,410 --> 00:02:59,000
dešinė M elementai garantuoja

60
00:02:59,000 --> 00:03:01,000
būti suskirstyti į jų teisingą vietą.

61
00:03:01,000 --> 00:03:02,280
Jei norite pamatyti šį sau,

62
00:03:02,280 --> 00:03:05,500
mes galime pabandyti jį visiškai atgalinio sąrašą [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Po vienu važiavimu per visą sąrašą,

64
00:03:08,220 --> 00:03:09,220
[Rašymo garso]

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
yra savo vietoje dešinė elementas 9.

67
00:03:21,250 --> 00:03:24,760
Po antrojo pass-through, 6 turės "burbuliukų-up"

68
00:03:24,760 --> 00:03:26,220
2. dešinė vieta.

69
00:03:26,220 --> 00:03:28,840
Dešinėje - 6 ir 9 - šie du elementai bus jų teisingas vietas

70
00:03:28,840 --> 00:03:30,580
po pirmųjų dviejų Pass-throughs.

71
00:03:30,580 --> 00:03:32,590
>> Taigi, kaip mes galime naudoti šį optimizuoti algoritmą?

72
00:03:32,590 --> 00:03:34,850
Na, po vieną iteracijoje masyvo

73
00:03:34,850 --> 00:03:37,690
mes ne iš tikrųjų reikia patikrinti dešinė elementas

74
00:03:37,690 --> 00:03:39,200
nes mes žinome, tai rūšiuojamos.

75
00:03:39,200 --> 00:03:43,050
Po dviejų iteracijų, mes žinome, tikrai dešinė du elementai yra.

76
00:03:43,050 --> 00:03:48,260
Taigi, apskritai, po k iteracijų per visą spektrą,

77
00:03:48,260 --> 00:03:51,550
tikrinti paskutinius k elementai yra nereikalingas, nes mes žinome,

78
00:03:51,550 --> 00:03:52,360
jie jau į reikiamą vietą.

79
00:03:52,360 --> 00:03:54,870
>> Taigi, jei jūs rūšiuojant n elementų masyvą,

80
00:03:54,870 --> 00:03:57,870
pirmajam iteracijos procesui - ty jūs turite rūšiuoti visi elementai - pirmasis N-0.

81
00:03:57,870 --> 00:04:04,170
Dėl antrosios iteracijos, jūs turite pažvelgti į visus elementus, tačiau paskutinį -

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

83
00:04:07,090 --> 00:04:10,520
Kitas optimizavimas gali būti patikrinti, ar sąrašas jau yra surūšiuoti

84
00:04:10,520 --> 00:04:11,710
po kiekvienos iteracijos.

85
00:04:11,710 --> 00:04:13,900
Jei jis jau rūšiuojamos, mums nereikia, kad daugiau iteracijų

86
00:04:13,900 --> 00:04:15,310
per sąrašą.

87
00:04:15,310 --> 00:04:16,220
Kaip mes galime tai padaryti?

88
00:04:16,220 --> 00:04:19,360
Na, jei mes neturime jokių pass-through sąrašo apsikeitimo sandorius,

89
00:04:19,360 --> 00:04:22,350
dabar jau aišku, kad šis sąrašas jau buvo surūšiuoti, nes mes neturėjome apsikeitimo nieko.

90
00:04:22,350 --> 00:04:24,160
Taigi mes tikrai neturite rūšiuoti vėl.

91
00:04:24,160 --> 00:04:27,960
>> Gal galėtumėte inicijuoti vėliavos kintamasis vadinamas "nėra rūšiuojamos"

92
00:04:27,960 --> 00:04:30,990
false ir pakeiskite ją "true", jei jūs turite apsikeitimo jokių įrodymų dėl

93
00:04:30,990 --> 00:04:32,290
vienas iš pasikartojančių per masyvo.

94
00:04:32,290 --> 00:04:35,350
Ar panašiai, kad skaitiklis suskaičiuoti, kiek apsikeitimo sandoriai jums padaryti

95
00:04:35,350 --> 00:04:37,040
bet kuriuo iteracijos.

96
00:04:37,040 --> 00:04:40,040
Yra iteracijos pabaigoje, jei tu negali apsikeitimo elementų,

97
00:04:40,040 --> 00:04:41,780
žinote, sąrašas jau yra rūšiuojami ir baigsite.

98
00:04:41,780 --> 00:04:44,090
Burbulas Rūšiuoti, kaip ir kiti rūšiavimo algoritmų, gali būti

99
00:04:44,090 --> 00:04:46,960
nežymiai dirbti bet kokius elementus, kurie turi užsakymo metodą.

100
00:04:46,960 --> 00:04:50,610
>> Tai reiškia, kad du elementai jūs turite būdas pasakyti, jei pirmasis

101
00:04:50,610 --> 00:04:53,770
yra didesnis nei yra lygi arba mažesnė už antrąją.

102
00:04:53,770 --> 00:04:56,870
Pavyzdžiui, galite rūšiuoti abėcėlės raidėmis, sakydamas

103
00:04:56,870 --> 00:05:00,520
kad a <b, b <c ir tt

104
00:05:00,520 --> 00:05:03,830
Arba jums gali rūšiuoti savaitės dienomis, sekmadienis yra mažiau nei pirmadienis

105
00:05:03,830 --> 00:05:05,110
kuris yra mažesnis nei antradienis.

106
00:05:05,110 --> 00:05:09,630
>> Burbulas Rūšiuoti jokiu būdu nėra labai efektyviai arba greito rūšiavimo algoritmą.

107
00:05:09,630 --> 00:05:12,370
Blogiausiu atveju Runtime Didelės O n ²

108
00:05:12,370 --> 00:05:14,810
nes jūs turite padaryti n iteracijų per sąrašo

109
00:05:14,810 --> 00:05:18,430
tikrina visus n elementų, kiekvienas pass-through, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Šios įsibėgėjimo laikas reiškia, kad kaip elementų jūs rūšiavimo didėja,

111
00:05:22,730 --> 00:05:24,330
vykdymo metu padidina kvadratin.

112
00:05:24,330 --> 00:05:27,330
>> Tačiau, jei efektyvumas nėra pagrindinis rūpestis savo programą

113
00:05:27,330 --> 00:05:29,550
arba jei jūs tik nedaug elementų rūšiavimas,

114
00:05:29,550 --> 00:05:31,660
galite rasti burbulas Rūšiuoti naudinga, nes

115
00:05:31,660 --> 00:05:33,360
tai vienas iš paprasčiausių rūšiavimo algoritmų suprasti

116
00:05:33,360 --> 00:05:34,250
ir kodas.

117
00:05:34,250 --> 00:05:37,270
Jis taip pat yra puikus būdas įgyti patirties su vertimu teorinis

118
00:05:37,270 --> 00:05:40,220
algoritmas faktinės veikiančios kodu.

119
00:05:40,220 --> 00:05:43,000
Gerai, kad burbulas Rūšiuoti Jums. Thanks for watching.

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