1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [BUBBLE RENDEZÉS]

2
00:00:02,840 --> 00:00:04,560
[JACKSON Steinkamp Harvard Egyetem]

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

4
00:00:08,000 --> 00:00:11,730
Bubble rendezése egy példa a rendezési algoritmus -

5
00:00:11,730 --> 00:00:14,460
azaz egy eljárást rendezéséhez egy sor Elemek

6
00:00:14,460 --> 00:00:15,840
növekvő vagy csökkenő sorrendben.

7
00:00:15,840 --> 00:00:18,710
Például, ha akart rendezni egy tömb, ami a számok

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], a helyes végrehajtása Bubble osztályozása visszatér a

9
00:00:23,060 --> 00:00:26,260
rendezett tömbben [2, 3, 5, 9], növekvő sorrendben.

10
00:00:26,260 --> 00:00:28,850
Most fogom elmagyarázni, hogyan pszeudokód az algoritmus működik.

11
00:00:28,850 --> 00:00:34,000
>> Tegyük fel, hogy mi válogatás egy listát az 5 egészek - 3, 2, 9, 6, és 5.

12
00:00:34,000 --> 00:00:37,650
Az algoritmus indul nézi most az első két elem, 3 és 2,

13
00:00:37,650 --> 00:00:40,850
és ellenőrzés, ha ők out of order egymáshoz képest.

14
00:00:40,850 --> 00:00:43,150
Ezek - 3 2-nél nagyobb.

15
00:00:43,150 --> 00:00:45,190
Ahhoz, hogy növekvő sorrendben kell lenniük a másik fordítva.

16
00:00:45,190 --> 00:00:46,610
Szóval, mi cserélni őket.

17
00:00:46,610 --> 00:00:49,760
Most a jegyzék néz ki: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Ezután nézzük meg a második és a harmadik elem, 3 és 9.

19
00:00:52,450 --> 00:00:55,770
Ők a megfelelő sorrendben egymáshoz képest.

20
00:00:55,770 --> 00:00:58,800
Azaz, a 3. kevesebb, mint 9, így az algoritmus nem cserélni őket.

21
00:00:58,800 --> 00:01:01,900
Ezután nézzük a 9 és 6. Ők elromlott.

22
00:01:01,900 --> 00:01:04,260
>> Szóval, meg kell cserélni őket, mert 9 nagyobb, mint 6.

23
00:01:04,260 --> 00:01:08,840
Végül nézzük meg az utolsó két egész, 9 és 5.

24
00:01:08,840 --> 00:01:10,850
Ők meg a rend, ezért kell őket cserélni.

25
00:01:10,850 --> 00:01:13,360
Miután az első teljes áthaladnak a listán,

26
00:01:13,360 --> 00:01:17,140
így néz ki: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Nem rossz. Már majdnem rendezve.

28
00:01:19,690 --> 00:01:22,450
De kell, hogy végig a listát újra a teljesen rendezve.

29
00:01:22,450 --> 00:01:29,250
Két kisebb, mint 3, így nem cserélni őket.

30
00:01:29,250 --> 00:01:31,700
>> Három a kisebb, mint 6, így nem cserélni őket.

31
00:01:31,700 --> 00:01:35,500
Hat több mint 5. Mi cserélték.

32
00:01:35,500 --> 00:01:38,460
Hat nem kevesebb mint 9. Nem cserélni.

33
00:01:38,460 --> 00:01:42,170
Miután a második lépésben át, úgy néz ki: [2, 3, 5, 6, 9]. Tökéletes.

34
00:01:42,170 --> 00:01:44,680
Most pedig írd azt pszeudokód.

35
00:01:44,680 --> 00:01:48,450
Alapvetően minden egyes elem a listán, meg kell nézni, hogy

36
00:01:48,450 --> 00:01:50,060
és az elem közvetlenül annak jobbra.

37
00:01:50,060 --> 00:01:53,420
Ha ők meghibásodott egymásnak megfelelően - azaz, ha a bal oldali elem

38
00:01:53,420 --> 00:01:56,810
nagyobb, mint az egyik a jobb - meg kell cserélni a két eleme van.

39
00:01:56,810 --> 00:02:01,270
>> Tesszük ezt minden egyes eleme a listáról, és tettünk egy menetben keresztül.

40
00:02:01,270 --> 00:02:05,160
Most már csak meg kell csinálni a pass-through elégszer, hogy biztosítsák a lista

41
00:02:05,160 --> 00:02:06,480
teljesen, megfelelően rendezve.

42
00:02:06,480 --> 00:02:08,889
De hányszor kell még át a listát

43
00:02:08,889 --> 00:02:10,400
garantálja, hogy készen vagyunk?

44
00:02:10,400 --> 00:02:14,730
Nos, a legrosszabb esetben is, ha egy teljesen hátra listát.

45
00:02:14,730 --> 00:02:17,840
Akkor tart számos át-átvezetéseket számával megegyező

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

47
00:02:19,730 --> 00:02:24,720
Ha ez nincs értelme ösztönösen, gondolom, egy egyszerű ügy - a lista [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Ez fog tartani az 1 pass-through rendezni helyesen.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - A legrosszabb eset az, hogy a 3 elem sorrendje hátrafelé,

50
00:02:33,060 --> 00:02:34,830
ez fog tartani 2 ismétléseket a rendezéshez.

51
00:02:34,830 --> 00:02:37,980
Miután egy iteráció, ez [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
A második hozamok a rendezett tömbben [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Szóval, tudod, soha nem kell, hogy menjen át a tömb, általában

54
00:02:43,350 --> 00:02:46,790
több, mint n-1-szer, ahol n az elemek száma a tömbben.

55
00:02:47,090 --> 00:02:50,470
Úgy hívják Bubble rendezése, mert a legnagyobb elemek hajlamosak a "buborék-up"

56
00:02:50,470 --> 00:02:51,950
jobbra elég gyorsan.

57
00:02:51,950 --> 00:02:53,980
Valójában ez az algoritmus nagyon érdekes viselkedést.

58
00:02:53,980 --> 00:02:57,410
>> Miután m iteráció az egész tömb,

59
00:02:57,410 --> 00:02:59,000
A jobb szélső m elemeket garantált

60
00:02:59,000 --> 00:03:01,000
kell rendezni a megfelelő helyre.

61
00:03:01,000 --> 00:03:02,280
Ha szeretné látni ezt magadnak,

62
00:03:02,280 --> 00:03:05,500
tudjuk próbálni egy teljesen hátra lista [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Miután az egyik átmegy a teljes lista

64
00:03:08,220 --> 00:03:09,220
[Hang az írás]

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
A jobb szélső elem 9 nyelven a megfelelő helyre.

67
00:03:21,250 --> 00:03:24,760
Miután a második pass-through, a 6 lesz "buborékoltatunk-up" a

68
00:03:24,760 --> 00:03:26,220
2. jobb szélső helyen.

69
00:03:26,220 --> 00:03:28,840
A két elem a jobb oldalon - 6 és 9 - lesz a megfelelő helyekre

70
00:03:28,840 --> 00:03:30,580
miután az első két pass-throughs.

71
00:03:30,580 --> 00:03:32,590
>> Szóval, hogyan lehet használni ezt, hogy optimalizálják az algoritmus?

72
00:03:32,590 --> 00:03:34,850
Nos, miután az egyik iteráció a tömb

73
00:03:34,850 --> 00:03:37,690
hogy valójában nem kell ellenőrizni a jobb szélső elem

74
00:03:37,690 --> 00:03:39,200
mert tudjuk, ez rendezve.

75
00:03:39,200 --> 00:03:43,050
Miután két iteráció, tudjuk róla, hogy a jobb szélső két elem a helyén van.

76
00:03:43,050 --> 00:03:48,260
Tehát, általánosságban, miután k iteráció keresztül a teljes tömb,

77
00:03:48,260 --> 00:03:51,550
ellenőrzése az utolsó k eleme feleslegessé vált, mivel tudjuk, hogy

78
00:03:51,550 --> 00:03:52,360
ők a megfelelő helyen már.

79
00:03:52,360 --> 00:03:54,870
>> Szóval, ha válogatás egy sor n elemek,

80
00:03:54,870 --> 00:03:57,870
az első iteráció - you'll kell rendezni összes elemet - az első n-0.

81
00:03:57,870 --> 00:04:04,170
A második iteráció, akkor meg kell nézni az összes elemet, de az utolsó -

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

83
00:04:07,090 --> 00:04:10,520
Egy másik optimalizálási lehet ellenőrizni, hogy a lista már rendezve

84
00:04:10,520 --> 00:04:11,710
után iteráció.

85
00:04:11,710 --> 00:04:13,900
Ha ez már rendezve, nem kell, hogy többé iteráció

86
00:04:13,900 --> 00:04:15,310
végig a listát.

87
00:04:15,310 --> 00:04:16,220
Hogyan tudjuk ezt megtenni?

88
00:04:16,220 --> 00:04:19,360
Nos, ha nem teszünk semmilyen swap egy pass-through a lista,

89
00:04:19,360 --> 00:04:22,350
világos, hogy a lista már rendezve, mert mi nem cserélni semmit.

90
00:04:22,350 --> 00:04:24,160
Így biztosan nem kell rendezni újra.

91
00:04:24,160 --> 00:04:27,960
>> Talán lehetett inicializálni a lobogó változó úgynevezett "nem válogatják szét" a

92
00:04:27,960 --> 00:04:30,990
false, és változtassa igaz, ha a swap olyan elemek

93
00:04:30,990 --> 00:04:32,290
1 iteráció a tömb.

94
00:04:32,290 --> 00:04:35,350
Vagy hasonlóképpen, hogy egy számláló, hány swap csinál

95
00:04:35,350 --> 00:04:37,040
bármely adott iteráció.

96
00:04:37,040 --> 00:04:40,040
A végén egy iteráció, ha nem cserélni bármely eleme,

97
00:04:40,040 --> 00:04:41,780
tudod, hogy a lista már rendezve, és kész.

98
00:04:41,780 --> 00:04:44,090
Bubble rendezése, mint a többi rendező algoritmus, lehet

99
00:04:44,090 --> 00:04:46,960
csípett dolgozni olyan elemeket, amelyek egy rendelési módszer.

100
00:04:46,960 --> 00:04:50,610
>> Ez azt jelenti, az adott két elem van egy módja annak, hogy azt mondják, ha az első

101
00:04:50,610 --> 00:04:53,770
nagyobb, egyenlő vagy kisebb, mint a második.

102
00:04:53,770 --> 00:04:56,870
Például, lehet rendezni az ábécé kimondásával

103
00:04:56,870 --> 00:05:00,520
hogy a <b, b <c, stb

104
00:05:00,520 --> 00:05:03,830
Vagy lehetne rendezni a hét, ahol vasárnap kevesebb mint hétfő

105
00:05:03,830 --> 00:05:05,110
ami kisebb, mint kedden.

106
00:05:05,110 --> 00:05:09,630
>> Bubble Rendezés egyáltalán nem valami hatékony és gyors válogató algoritmus.

107
00:05:09,630 --> 00:05:12,370
A legrosszabb eset runtime Big O n ²

108
00:05:12,370 --> 00:05:14,810
mert van, hogy n iteráció egy listát

109
00:05:14,810 --> 00:05:18,430
Ellenőrzi az összes n elem minden pass-through, NxN = n ².

110
00:05:18,430 --> 00:05:22,730
Ez futási idő azt jelenti, hogy az elemek száma, amit válogatás növekszik,

111
00:05:22,730 --> 00:05:24,330
a futási idő négyzetesen növekszik.

112
00:05:24,330 --> 00:05:27,330
>> De ha a hatékonyság nem egyik fő törekvése a program

113
00:05:27,330 --> 00:05:29,550
vagy ha csak egy kis válogatás számos elemet,

114
00:05:29,550 --> 00:05:31,660
lehet, hogy talál Bubble Sort hasznos, mert

115
00:05:31,660 --> 00:05:33,360
ez az egyik legegyszerűbb rendezési algoritmusok megérteni

116
00:05:33,360 --> 00:05:34,250
és a kódot.

117
00:05:34,250 --> 00:05:37,270
Ez is egy nagyszerű módja annak, hogy tapasztalatokat fordítására elméleti

118
00:05:37,270 --> 00:05:40,220
algoritmus tényleges működését kódot.

119
00:05:40,220 --> 00:05:43,000
Nos, ez Bubble osztályozása az Ön számára. Köszönöm, hogy néz.

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