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

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP Harvard Universiteit]

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

4
00:00:08,000 --> 00:00:11,730
Bubble Sorteer is 'n voorbeeld van 'n sorteer algoritme -

5
00:00:11,730 --> 00:00:14,460
dit is 'n proses vir die sortering van 'n stel van die elemente in

6
00:00:14,460 --> 00:00:15,840
stygende of dalende volgorde.

7
00:00:15,840 --> 00:00:18,710
Byvoorbeeld, as jy wou 'n skikking te sorteer uit van die getalle

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], sou 'n korrekte implementering van die Bubble Sorteer die standaard van die

9
00:00:23,060 --> 00:00:26,260
gesorteer array [2, 3, 5, 9 in stygende orde.

10
00:00:26,260 --> 00:00:28,850
Nou, ek gaan om te verduidelik die pseudokode hoe die algoritme werk.

11
00:00:28,850 --> 00:00:34,000
>> Kom ons sê dat ons 'n lys van 5 heelgetalle te sorteer - 3, 2, 9, 6, en 5.

12
00:00:34,000 --> 00:00:37,650
Die algoritme begin deur te kyk na die eerste twee elemente, 3 en 2,

13
00:00:37,650 --> 00:00:40,850
en te keur as hulle uit van orde relatief tot mekaar.

14
00:00:40,850 --> 00:00:43,150
Hulle is 3 groter as 2 is.

15
00:00:43,150 --> 00:00:45,190
Te wees in stygende volgorde, moet hulle die ander manier om.

16
00:00:45,190 --> 00:00:46,610
So, ons ruil hulle.

17
00:00:46,610 --> 00:00:49,760
Nou is die lys lyk soos hierdie: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Volgende kyk ons ​​na die tweede en derde elemente, 3 en 9.

19
00:00:52,450 --> 00:00:55,770
Hulle is in die korrekte volgorde relatief tot mekaar.

20
00:00:55,770 --> 00:00:58,800
Dit is, 3 is minder as 9 sodat die algoritme hulle nie ruil.

21
00:00:58,800 --> 00:01:01,900
Volgende, ons kyk op 9 en 6. Hulle is buite orde.

22
00:01:01,900 --> 00:01:04,260
>> So, ons nodig het om hulle te ruil, want 9 is meer as 6.

23
00:01:04,260 --> 00:01:08,840
Ten slotte, ons kyk na die laaste twee heelgetalle, 9 en 5.

24
00:01:08,840 --> 00:01:10,850
Hulle is buite orde, so hulle moet omgeruil word.

25
00:01:10,850 --> 00:01:13,360
Na die eerste volledige slaag deur die lys,

26
00:01:13,360 --> 00:01:17,140
dit lyk soos hierdie: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Nie sleg nie. Dit is byna gesorteer.

28
00:01:19,690 --> 00:01:22,450
Maar ons moet loop weer deur die lys om dit heeltemal gesorteer te kry.

29
00:01:22,450 --> 00:01:29,250
Twee is minder as 3, so ons ruil hulle nie.

30
00:01:29,250 --> 00:01:31,700
>> Drie is minder as 6, so ons ruil hulle nie.

31
00:01:31,700 --> 00:01:35,500
Ses is groter as 5. Ons verruil.

32
00:01:35,500 --> 00:01:38,460
Ses minder as 9. Ons ruil nie.

33
00:01:38,460 --> 00:01:42,170
Na die tweede deurtrek, dit lyk soos hierdie: [2, 3, 5, 6, 9]. Perfect.

34
00:01:42,170 --> 00:01:44,680
Nou, laat ons skryf dit in pseudokode.

35
00:01:44,680 --> 00:01:48,450
Basies, vir elke element in die lys, ons nodig het om te kyk na dit

36
00:01:48,450 --> 00:01:50,060
en die element direk tot sy reg.

37
00:01:50,060 --> 00:01:53,420
As hulle buite werking is relatief tot mekaar - dit is, as die element aan die linkerkant

38
00:01:53,420 --> 00:01:56,810
is groter as die een aan die regter - ons moet ruil die twee elemente.

39
00:01:56,810 --> 00:02:01,270
>> Ons doen dit vir elke element van die lys, en ons het een deurtrek.

40
00:02:01,270 --> 00:02:05,160
Nou moet ons net die pass-through genoeg keer om te doen om die lys om te verseker

41
00:02:05,160 --> 00:02:06,480
is ten volle, behoorlik gesorteer.

42
00:02:06,480 --> 00:02:08,889
Maar hoeveel keer het ons het om te slaag deur die lys te

43
00:02:08,889 --> 00:02:10,400
waarborg dat ons gedoen het?

44
00:02:10,400 --> 00:02:14,730
Wel, die ergste geval scenario is as ons 'n heeltemal agteruit lys.

45
00:02:14,730 --> 00:02:17,840
Dan neem 'n aantal van die slaag-throughs gelyk aan die aantal

46
00:02:17,840 --> 00:02:19,730
elemente N-1.

47
00:02:19,730 --> 00:02:24,720
As dit nie sin maak nie intuïtief, dink van 'n eenvoudige geval - die lys [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Dit gaan 'n pass-through neem om te korrek te sorteer.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Die ergste geval is dat met 3 elemente gesorteer agteruit,

50
00:02:33,060 --> 00:02:34,830
dit gaan 2 iterasies te neem om te sorteer.

51
00:02:34,830 --> 00:02:37,980
Na een iterasie, dit is [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Die tweede opbrengste die gesorteerde array [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
So jy weet dat jy nooit weer hoef te gaan deur middel van die skikking, in die algemeen,

54
00:02:43,350 --> 00:02:46,790
meer as N-1 keer, waar n die aantal elemente in die skikking.

55
00:02:47,090 --> 00:02:50,470
Dit is genoem Bubble Sorteer omdat die grootste elemente is geneig om te "borrel-up"

56
00:02:50,470 --> 00:02:51,950
redelik vinnig aan die regterkant.

57
00:02:51,950 --> 00:02:53,980
In werklikheid, hierdie algoritme het 'n baie interessante gedrag.

58
00:02:53,980 --> 00:02:57,410
>> Na m iterasies deur die hele skikking,

59
00:02:57,410 --> 00:02:59,000
die regterkantste m elemente is gewaarborg

60
00:02:59,000 --> 00:03:01,000
word gesorteer in hulle regte plek.

61
00:03:01,000 --> 00:03:02,280
As jy wil om dit te sien vir jouself,

62
00:03:02,280 --> 00:03:05,500
ons kan probeer om dit op 'n heeltemal agteruit lys [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Na een keer deur die hele lys,

64
00:03:08,220 --> 00:03:09,220
[Geluid van skrif]

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
die mees regse element 9 is in sy behoorlike plek.

67
00:03:21,250 --> 00:03:24,760
Na die tweede pass-through, sal die 6 het geborrel-up "aan die

68
00:03:24,760 --> 00:03:26,220
tweede regterkantste plek.

69
00:03:26,220 --> 00:03:28,840
Die twee elemente op die regte - 6 en 9 - sal wees in hulle korrekte plekke

70
00:03:28,840 --> 00:03:30,580
na die eerste twee pass-throughs.

71
00:03:30,580 --> 00:03:32,590
>> Dus, hoe kan ons dit gebruik om die algoritme te optimaliseer?

72
00:03:32,590 --> 00:03:34,850
Wel, na een iterasie deur die skikking

73
00:03:34,850 --> 00:03:37,690
ons nie eintlik nodig het om seker te maak die mees regse element

74
00:03:37,690 --> 00:03:39,200
omdat ons weet dit is gesorteer.

75
00:03:39,200 --> 00:03:43,050
Na twee iterasies, ons weet vir seker dat die regterkantste twee elemente is in plek.

76
00:03:43,050 --> 00:03:48,260
So, in die algemeen, na k iterasies deur die volle verskeidenheid,

77
00:03:48,260 --> 00:03:51,550
die beheer van die laaste k elemente is oorbodig want ons weet

78
00:03:51,550 --> 00:03:52,360
hulle is reeds op die regte plek.

79
00:03:52,360 --> 00:03:54,870
>> So as jy die sortering van 'n verskeidenheid van n elemente,

80
00:03:54,870 --> 00:03:57,870
op die eerste iterasie - you'll het al die elemente uit te sorteer - die eerste n-0.

81
00:03:57,870 --> 00:04:04,170
Op die tweede iterasie, sal jy het om te kyk na al die elemente, maar die laaste -

82
00:04:04,170 --> 00:04:07,090
die eerste N-1.

83
00:04:07,090 --> 00:04:10,520
Nog 'n optimalisering kan wees om seker te maak indien die lys is reeds gesorteer

84
00:04:10,520 --> 00:04:11,710
na elke iterasie.

85
00:04:11,710 --> 00:04:13,900
As dit reeds gesorteer is, het ons nie nodig nie meer iterasies te maak

86
00:04:13,900 --> 00:04:15,310
deur die lys.

87
00:04:15,310 --> 00:04:16,220
Hoe kan ons dit doen?

88
00:04:16,220 --> 00:04:19,360
Wel, as ons maak geen swaps op 'n pass-through van die lys,

89
00:04:19,360 --> 00:04:22,350
dit is duidelik dat die lys is reeds gesorteer is, want ons het niks ruil.

90
00:04:22,350 --> 00:04:24,160
So het ons beslis nie om weer te sorteer.

91
00:04:24,160 --> 00:04:27,960
>> Miskien kan jy 'n vlag veranderlike genoem nie gesorteer 'to inisialiseer

92
00:04:27,960 --> 00:04:30,990
vals en verander dit na ware indien u enige elemente op te ruil

93
00:04:30,990 --> 00:04:32,290
een iterasie deur die skikking.

94
00:04:32,290 --> 00:04:35,350
Of soortgelyk, maak 'n toonbank om te tel hoeveel swaps jy maak

95
00:04:35,350 --> 00:04:37,040
op enige gegewe iterasie.

96
00:04:37,040 --> 00:04:40,040
Aan die einde van 'n iterasie, as jy nie enige van die elemente ruil,

97
00:04:40,040 --> 00:04:41,780
jy weet die lys is reeds gesorteer en wat jy gedoen het.

98
00:04:41,780 --> 00:04:44,090
Bubble sorteer, soos ander sorteer-algoritmes, kan

99
00:04:44,090 --> 00:04:46,960
tweaked om te werk vir enige elemente wat 'n bestel metode.

100
00:04:46,960 --> 00:04:50,610
>> Dit is twee elemente wat jy het 'n manier om te sê as die eerste een

101
00:04:50,610 --> 00:04:53,770
is groter as, gelyk aan of minder as die tweede.

102
00:04:53,770 --> 00:04:56,870
Byvoorbeeld, kan jy die letters van die alfabet sorteer deur te sê

103
00:04:56,870 --> 00:05:00,520
dat a <b, b <c, ens.

104
00:05:00,520 --> 00:05:03,830
Of jy kan sorteer dae van die week waar Sondag is minder as Maandag

105
00:05:03,830 --> 00:05:05,110
wat is minder as Dinsdag.

106
00:05:05,110 --> 00:05:09,630
>> Bubble Sorteer is geensins 'n baie doeltreffende of vinnig sorteer algoritme.

107
00:05:09,630 --> 00:05:12,370
Die ergste-geval looptyd is Big O van n ²

108
00:05:12,370 --> 00:05:14,810
want jy het 'n iterasies te maak deur middel van 'n lys

109
00:05:14,810 --> 00:05:18,430
kontrolering van alle n elemente elke pass-through, NxN = n ².

110
00:05:18,430 --> 00:05:22,730
Hierdie looptyd beteken dat as die aantal elemente wat jy verhogings jy sorteer,

111
00:05:22,730 --> 00:05:24,330
die loop van die tyd verhoog kwadratisch.

112
00:05:24,330 --> 00:05:27,330
>> Maar as doeltreffendheid is nie 'n groot bron van kommer vir jou program

113
00:05:27,330 --> 00:05:29,550
of as jy net die sortering van 'n klein aantal van die elemente,

114
00:05:29,550 --> 00:05:31,660
dalk vind jy Bubble Sorteer nuttig omdat

115
00:05:31,660 --> 00:05:33,360
dit is een van die eenvoudigste sorteer-algoritmes om te verstaan

116
00:05:33,360 --> 00:05:34,250
en te kodeer.

117
00:05:34,250 --> 00:05:37,270
Dit is ook 'n goeie manier om ervaring te kry om met die vertaling van 'n teoretiese

118
00:05:37,270 --> 00:05:40,220
algoritme in die werklike werking kode.

119
00:05:40,220 --> 00:05:43,000
Wel, dit is Bubble Sorteer vir jou. Dankie vir jou kyk.

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