1
00:00:00,000 --> 00:00:03,360
>> [Zenelejátszási]

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

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Rendben,
buborékos rendezést egy algoritmus

4
00:00:06,730 --> 00:00:08,730
segítségével rendezni egy sor elemet.

5
00:00:08,730 --> 00:00:10,850
Vessünk egy pillantást, hogyan működik.

6
00:00:10,850 --> 00:00:13,240
>> Tehát az alapötlet mögött
buborékos rendezést ez.

7
00:00:13,240 --> 00:00:17,340
Mi általában szeretnének feljebb
értékes elemei általában a jobb,

8
00:00:17,340 --> 00:00:20,340
és engedje értékes elemek általában
balra, ahogy várnánk.

9
00:00:20,340 --> 00:00:23,256
Szeretnénk, ha az alacsonyabb dolgokat, hogy a
Az elején, és a magasabb dolgok

10
00:00:23,256 --> 00:00:24,970
hogy a végén.

11
00:00:24,970 --> 00:00:26,130
>> Hogyan tudjuk ezt megtenni?

12
00:00:26,130 --> 00:00:28,040
Nos pszeudokód kódot,
mondhatnánk, nézzük

13
00:00:28,040 --> 00:00:30,320
állítsa a swap számláló nem nulla értéket.

14
00:00:30,320 --> 00:00:32,570
Meglátjuk, hogy miért csináljuk, hogy egy másodperc.

15
00:00:32,570 --> 00:00:36,090
És akkor ismételje meg a következő
folyamatot, amíg a swap-számláló 0,

16
00:00:36,090 --> 00:00:39,910
vagy amíg nem teszünk csereügyletek egyáltalán.

17
00:00:39,910 --> 00:00:43,170
>> Állítsa vissza a swap-számláló
0, ha még nincs 0.

18
00:00:43,170 --> 00:00:46,420
Akkor nézd meg minden
szomszédos pár elemekkel.

19
00:00:46,420 --> 00:00:49,550
Ha e két elem
Nem azért, cserélni őket,

20
00:00:49,550 --> 00:00:51,620
és adjunk hozzá 1 a swap számláló.

21
00:00:51,620 --> 00:00:53,870
Ha még nem gondolkodik
ezt, mielőtt képzelni,

22
00:00:53,870 --> 00:00:57,471
észre, hogy ez fog mozogni az alacsonyabb
értékes elemek balra

23
00:00:57,471 --> 00:01:00,720
és a magasabb értékű elemek a jogot,
hatékonyan teszi, amit akarunk csinálni,

24
00:01:00,720 --> 00:01:03,940
ami mozog azoknak a csoportoknak
Az elemek ilyen módon.

25
00:01:03,940 --> 00:01:07,035
Nézzük elképzelni, hogy ez a
nézhet a mi tömb

26
00:01:07,035 --> 00:01:10,504
hogy mi használt teszt
ki ezeket az algoritmusokat.

27
00:01:10,504 --> 00:01:13,420
Van egy rendezetlen tömb újra itt,
által jelzett összes elem

28
00:01:13,420 --> 00:01:14,840
hogy a piros.

29
00:01:14,840 --> 00:01:17,970
És tudom a swap-counter
hogy egy nem nulla értéket.

30
00:01:17,970 --> 00:01:20,610
Én önkényesen választotta
negatív 1-- ez nem 0.

31
00:01:20,610 --> 00:01:23,840
Szeretnénk megismételni ezt a folyamatot
amíg a swap-számláló 0.

32
00:01:23,840 --> 00:01:26,540
Ez az oka annak megadom a swap-
számláló néhány nem nulla értéket,

33
00:01:26,540 --> 00:01:29,400
mert egyébként az
swap-számláló 0 lenne.

34
00:01:29,400 --> 00:01:31,610
Akkor nem is kezdődik a
folyamat az algoritmus.

35
00:01:31,610 --> 00:01:33,610
Tehát ismét a lépéseket are--
állítsa vissza a swap számláló

36
00:01:33,610 --> 00:01:37,900
0, akkor nézd meg minden szomszédos
pár, és ha ők ki annak érdekében,

37
00:01:37,900 --> 00:01:40,514
cserélni őket, és adjunk hozzá 1
a swap számláló.

38
00:01:40,514 --> 00:01:41,680
Kezdjük ezt a folyamatot.

39
00:01:41,680 --> 00:01:44,430
Tehát az első dolog, amit tennie,
mi meg a swap-számlálóját 0,

40
00:01:44,430 --> 00:01:46,660
és akkor kezdeni
minden egyes szomszédos párja.

41
00:01:46,660 --> 00:01:49,140
>> Tehát először kezdeni a 5 és 2.

42
00:01:49,140 --> 00:01:52,410
Látjuk, hogy ezek közül
rendelni, és így cserélni őket.

43
00:01:52,410 --> 00:01:53,830
És mi adjunk hozzá 1 a swap számláló.

44
00:01:53,830 --> 00:01:57,860
Tehát most mi swap-számláló értéke 1,
2, illetve 5 vannak kapcsolva.

45
00:01:57,860 --> 00:01:59,370
Most ismételjük meg a folyamatot újra.

46
00:01:59,370 --> 00:02:03,540
>> Nézzük a következő szomszédos pár,
5 és 1-- ők is elromlott,

47
00:02:03,540 --> 00:02:06,960
így cserélni őket, és adjunk hozzá
1 a swap számláló.

48
00:02:06,960 --> 00:02:08,900
Akkor nézzük 5 és 3.

49
00:02:08,900 --> 00:02:13,830
Ők elromlott, így csere
őket, és adjunk hozzá 1 a swap számláló.

50
00:02:13,830 --> 00:02:15,550
Akkor nézzük az 5. és 6..

51
00:02:15,550 --> 00:02:18,630
Ők annak érdekében, így valójában nem
kell cserélni semmit ebben az időben.

52
00:02:18,630 --> 00:02:20,250
Akkor nézd meg a 6. és a 4.

53
00:02:20,250 --> 00:02:24,920
Ők is elromlott, így csere
őket, és adjunk hozzá 1 a swap számláló.

54
00:02:24,920 --> 00:02:26,230
>> Most észre, mi történt.

55
00:02:26,230 --> 00:02:29,514
Már költözött 6 egészen a végéig.

56
00:02:29,514 --> 00:02:32,180
Tehát a kiválasztási sorrend, ha már
Látható, hogy a videót, amit tett,

57
00:02:32,180 --> 00:02:35,290
Végül aztán a
legkisebb eleme épület

58
00:02:35,290 --> 00:02:39,640
A rendezett tömbben alapvetően
balról jobbra, a legkisebbtől a legnagyobb.

59
00:02:39,640 --> 00:02:43,200
Abban az esetben, buborékos rendezést, ha mi vagyunk
ezt követően adott algoritmus,

60
00:02:43,200 --> 00:02:46,720
vagyunk valójában lesz az épület
A rendezett tömbben jobbról

61
00:02:46,720 --> 00:02:49,100
balra, legnagyobb a legkisebb.

62
00:02:49,100 --> 00:02:53,840
Mi már hatékonyan vezetünk 6, a
legnagyobb értéke, egészen a végéig.

63
00:02:53,840 --> 00:02:56,165
>> És így most már kijelentem
hogy mely válogatni,

64
00:02:56,165 --> 00:02:59,130
és a jövőben iterations--
megy át a tömb again--

65
00:02:59,130 --> 00:03:01,280
nem kell figyelembe vennie a 6. többé.

66
00:03:01,280 --> 00:03:03,850
Elég, ha csak úgy
A rendezetlen elemek

67
00:03:03,850 --> 00:03:06,299
ha keresünk szomszédos pár.

68
00:03:06,299 --> 00:03:08,340
Szóval mi befejeztük az egyik
áthaladnak buborékos rendezést.

69
00:03:08,340 --> 00:03:11,941
Tehát most megyünk vissza a kérdésre,
ismételjük, amíg a swap számláló 0.

70
00:03:11,941 --> 00:03:13,690
Nos a swap counter
4, így fogunk

71
00:03:13,690 --> 00:03:15,410
ismételgetni ezt a folyamatot újra.

72
00:03:15,410 --> 00:03:19,180
>> Megyünk vissza a swap számláló
0, és nézd meg két szomszédos.

73
00:03:19,180 --> 00:03:21,890
Szóval kezdjük a 2. és 1-- ők
elromlott, így cserélni őket

74
00:03:21,890 --> 00:03:23,620
és mi adjuk hozzá 1 a swap számláló.

75
00:03:23,620 --> 00:03:25,490
A 2. és 3., ők érdekében.

76
00:03:25,490 --> 00:03:27,060
Nem kell semmit tennie.

77
00:03:27,060 --> 00:03:28,420
3 és 5 rendben vannak.

78
00:03:28,420 --> 00:03:30,150
Nem kell semmit ott.

79
00:03:30,150 --> 00:03:32,515
>> 5 és 4, ezek ki
a rend, és ezért

80
00:03:32,515 --> 00:03:35,130
kell cserélni őket, és adjunk hozzá
1 a swap számláló.

81
00:03:35,130 --> 00:03:38,880
És most már átkerült az 5.,
A következő legnagyobb eleme,

82
00:03:38,880 --> 00:03:40,920
hogy a végén a szelektálatlan rész.

83
00:03:40,920 --> 00:03:44,360
Így már hívni, hogy
része a rendezve rész.

84
00:03:44,360 --> 00:03:47,180
>> Most már nézi a
képernyőn, és valószínűleg meg tudja mondani,

85
00:03:47,180 --> 00:03:50,130
akárcsak én, hogy a tömb
rendezve most.

86
00:03:50,130 --> 00:03:51,820
De nem tudjuk bizonyítani, hogy még.

87
00:03:51,820 --> 00:03:54,359
Nincs garancia
hogy ez válogatni.

88
00:03:54,359 --> 00:03:56,900
De ez az, ahol a swap
számláló fog jöhet számításba.

89
00:03:56,900 --> 00:03:59,060
>> Így már elkészült egy menetben.

90
00:03:59,060 --> 00:04:00,357
A swap-számláló 2.

91
00:04:00,357 --> 00:04:02,190
Mi is így fogjuk megismételni
ezt a folyamatot újra,

92
00:04:02,190 --> 00:04:04,290
ismételjük, amíg a swap számláló 0.

93
00:04:04,290 --> 00:04:05,550
Állítsa vissza a swap-számlálóját 0.

94
00:04:05,550 --> 00:04:06,820
Szóval majd vissza azt.

95
00:04:06,820 --> 00:04:09,810
>> Most nézd meg két szomszédos.

96
00:04:09,810 --> 00:04:11,880
Ez annak érdekében, 1 és 2.

97
00:04:11,880 --> 00:04:13,590
A 2. és 3. rendben vannak.

98
00:04:13,590 --> 00:04:15,010
A 3. és 4. érdekében.

99
00:04:15,010 --> 00:04:19,250
Tehát ezen a ponton, észre Elkészítettük
néztem minden szomszédos pár,

100
00:04:19,250 --> 00:04:22,530
de a swap-számláló még mindig 0.

101
00:04:22,530 --> 00:04:25,520
>> Ha nem kell váltani
Azon elemek, akkor

102
00:04:25,520 --> 00:04:28,340
kell lennie annak érdekében, azáltal,
értelmében ezt a folyamatot.

103
00:04:28,340 --> 00:04:32,000
És így a hatásfok a fajta,
hogy számítógépes szakemberek szeretik,

104
00:04:32,000 --> 00:04:35,560
A most már kijelentem
az egész tömbnek kell

105
00:04:35,560 --> 00:04:38,160
válogatni, mert nem
meg kell cserélni minden eleme.

106
00:04:38,160 --> 00:04:40,380
Ez nagyon szép.

107
00:04:40,380 --> 00:04:43,260
>> Szóval mi a legrosszabb esetben
forgatókönyv buborékos rendezést?

108
00:04:43,260 --> 00:04:46,240
A legrosszabb esetben a tömb
teljesen fordított sorrendben,

109
00:04:46,240 --> 00:04:49,870
és ezért kell minden buborék
A nagy elemek minden

110
00:04:49,870 --> 00:04:51,780
Az utat az egész tömböt.

111
00:04:51,780 --> 00:04:55,350
És mi is hatékonyan kell
buborék összes kis elemek vissza

112
00:04:55,350 --> 00:04:57,050
végig az egész tömb is.

113
00:04:57,050 --> 00:05:01,950
Tehát minden egyes n elem kell mozognia
szerte az összes többi N elemekkel.

114
00:05:01,950 --> 00:05:04,102
Szóval ez a legrosszabb forgatókönyv.

115
00:05:04,102 --> 00:05:05,810
A legjobb esetben
forgatókönyv bár ez

116
00:05:05,810 --> 00:05:07,880
kissé eltér a kiválasztási sorrend.

117
00:05:07,880 --> 00:05:10,040
A tömb már
válogatni, mikor megyünk.

118
00:05:10,040 --> 00:05:12,550
Nem kell, hogy bármilyen
csereügyletek az első menetben.

119
00:05:12,550 --> 00:05:14,940
Tehát lehet, hogy meg kell nézni
A kevesebb elem, ugye?

120
00:05:14,940 --> 00:05:18,580
Nem kell megismételni ezt
ahol számos alkalommal több.

121
00:05:18,580 --> 00:05:19,540
>> Szóval mit is jelent ez?

122
00:05:19,540 --> 00:05:22,390
Szóval mi a legrosszabb forgatókönyv
A buborékos rendezést, és mi

123
00:05:22,390 --> 00:05:25,330
A legjobb esetben a buborékos rendezést?

124
00:05:25,330 --> 00:05:27,770
Találta ki ezt?

125
00:05:27,770 --> 00:05:32,420
A legrosszabb esetben, ha a közelítéseket
minden az n elem n-szer.

126
00:05:32,420 --> 00:05:34,220
Tehát a legrosszabb eset n faragva.

127
00:05:34,220 --> 00:05:36,550
>> Ha a tömb tökéletesen
szétválogatott mégis, akkor csak

128
00:05:36,550 --> 00:05:38,580
meg kell nézni az egyes
az elemek egyszer.

129
00:05:38,580 --> 00:05:42,670
És ha a swap számláló még mindig 0,
akkor lehet mondani, ez a tömb rendezve.

130
00:05:42,670 --> 00:05:45,780
És így a legjobb esetben, ez
sokkal jobb, mint kiválasztási

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

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

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

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