1
00:00:00,000 --> 00:00:03,360
>> [MUSIK SPELA]

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

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Okej, så
bubbelsortering är en algoritm

4
00:00:06,730 --> 00:00:08,730
du kan använda för att sortera en rad faktorer.

5
00:00:08,730 --> 00:00:10,850
Låt oss ta en titt på hur det fungerar.

6
00:00:10,850 --> 00:00:13,240
>> Så grundidén bakom
bubbelsortering är detta.

7
00:00:13,240 --> 00:00:17,340
Vi vill i allmänhet att röra sig högre
värderade element i allmänhet till höger,

8
00:00:17,340 --> 00:00:20,340
och lägre värderade element i allmänhet
till vänster, som vi skulle förvänta oss.

9
00:00:20,340 --> 00:00:23,256
Vi vill att lägre saker att vara på
början, och de högre saker

10
00:00:23,256 --> 00:00:24,970
att vara i slutet.

11
00:00:24,970 --> 00:00:26,130
>> Hur gör vi detta?

12
00:00:26,130 --> 00:00:28,040
Väl i pseudokod kod,
Vi kan säga, låt oss

13
00:00:28,040 --> 00:00:30,320
ange en swap mot en icke-noll.

14
00:00:30,320 --> 00:00:32,570
Vi får se varför vi gör det i en sekund.

15
00:00:32,570 --> 00:00:36,090
Och då är vi upprepa följande
processen tills swap räknaren är 0,

16
00:00:36,090 --> 00:00:39,910
eller tills vi gör inga swappar alls.

17
00:00:39,910 --> 00:00:43,170
>> Återställ swap mot
0 om den inte redan är 0.

18
00:00:43,170 --> 00:00:46,420
Så titta på varje
intilliggande par av element.

19
00:00:46,420 --> 00:00:49,550
Om dessa två element är
inte är i ordning, byta dem,

20
00:00:49,550 --> 00:00:51,620
och tillsätt en på växlingsräknaren.

21
00:00:51,620 --> 00:00:53,870
Om du funderar på
detta innan du visualisera det,

22
00:00:53,870 --> 00:00:57,471
märka att detta kommer att flytta lägre
värderade element till vänster

23
00:00:57,471 --> 00:01:00,720
och högre värderade element till höger,
effektivt gör vad vi vill göra,

24
00:01:00,720 --> 00:01:03,940
vilket är flytta dessa grupper
element på detta sätt.

25
00:01:03,940 --> 00:01:07,035
Låt oss visualisera hur detta
kan se med hjälp av vår array

26
00:01:07,035 --> 00:01:10,504
som vi använde för att testa
ut dessa algoritmer.

27
00:01:10,504 --> 00:01:13,420
Vi har en osorterad array här igen,
indikeras av alla elementen

28
00:01:13,420 --> 00:01:14,840
vara i rött.

29
00:01:14,840 --> 00:01:17,970
Och jag ställer min swap disk
till ett värde skilt från noll.

30
00:01:17,970 --> 00:01:20,610
Jag godtyckligt valde
negativt 1-- det är inte 0.

31
00:01:20,610 --> 00:01:23,840
Vi vill upprepa denna process
tills swap räknaren är 0.

32
00:01:23,840 --> 00:01:26,540
Detta är anledningen till att jag in min swap
mot vissa icke-nollvärde,

33
00:01:26,540 --> 00:01:29,400
eftersom annars
swap disk skulle vara 0.

34
00:01:29,400 --> 00:01:31,610
Vi skulle inte ens börja
förfarandet enligt algoritmen.

35
00:01:31,610 --> 00:01:33,610
Så återigen, stegen är--
återställa swap räknaren

36
00:01:33,610 --> 00:01:37,900
0, sedan titta på varje intilliggande
par, och om de är i ordning,

37
00:01:37,900 --> 00:01:40,514
byta dem, och tillsätt 1
till swap räknaren.

38
00:01:40,514 --> 00:01:41,680
Så låt oss börja den här processen.

39
00:01:41,680 --> 00:01:44,430
Så det första vi gör är
vi sätter swap mot 0,

40
00:01:44,430 --> 00:01:46,660
och sedan börjar vi ser
vid varje angränsande par.

41
00:01:46,660 --> 00:01:49,140
>> Så vi först börja titta på 5 och 2.

42
00:01:49,140 --> 00:01:52,410
Vi ser att de är ute ur
ordning och så vi byta dem.

43
00:01:52,410 --> 00:01:53,830
Och vi lägger 1 till swap räknaren.

44
00:01:53,830 --> 00:01:57,860
Så nu vår swap disk är en,
och 2 och 5 har kopplats.

45
00:01:57,860 --> 00:01:59,370
Nu är vi upprepa processen igen.

46
00:01:59,370 --> 00:02:03,540
>> Vi tittar på nästa intilliggande par,
5 och 1-- de är också i ordning,

47
00:02:03,540 --> 00:02:06,960
så vi byta dem och lägg
1 till swap räknaren.

48
00:02:06,960 --> 00:02:08,900
Sedan tittar vi på 5 och 3.

49
00:02:08,900 --> 00:02:13,830
De är i ordning, så vi byta
dem och vi lägger en till swap räknaren.

50
00:02:13,830 --> 00:02:15,550
Sedan tittar vi på 5 och 6.

51
00:02:15,550 --> 00:02:18,630
De är i ordning, så vi egentligen inte
behöver byta något den här gången.

52
00:02:18,630 --> 00:02:20,250
Sedan tittar vi på 6 och 4.

53
00:02:20,250 --> 00:02:24,920
De är också i ordning, så vi byta
dem och vi lägger en till swap räknaren.

54
00:02:24,920 --> 00:02:26,230
>> Nu märker vad som har hänt.

55
00:02:26,230 --> 00:02:29,514
Vi har flyttat 6 hela vägen till slutet.

56
00:02:29,514 --> 00:02:32,180
Så i valet sort, om du har
sett att video, vad vi gjorde var

57
00:02:32,180 --> 00:02:35,290
Vi hamnade flytta
minsta element i byggnaden

58
00:02:35,290 --> 00:02:39,640
den sorterade arrayen huvudsakligen från
från vänster till höger, minsta till största.

59
00:02:39,640 --> 00:02:43,200
I fallet med bubbelsortering, om vi är
följer efter denna särskilda algoritm,

60
00:02:43,200 --> 00:02:46,720
vi faktiskt kommer att bygga
den sorterade arrayen från höger

61
00:02:46,720 --> 00:02:49,100
till vänster, största till minsta.

62
00:02:49,100 --> 00:02:53,840
Vi har faktiskt bubblade 6, den
största värde, hela vägen till slutet.

63
00:02:53,840 --> 00:02:56,165
>> Och så vi kan nu förklara
att detta är sorterad,

64
00:02:56,165 --> 00:02:59,130
och i framtiden iterations--
går igenom arrayen igen--

65
00:02:59,130 --> 00:03:01,280
Vi behöver inte tänka på sex längre.

66
00:03:01,280 --> 00:03:03,850
Vi behöver bara tänka på
de osorterade element

67
00:03:03,850 --> 00:03:06,299
När vi tittar på angränsande par.

68
00:03:06,299 --> 00:03:08,340
Så vi har avslutat ett
passera genom bubbelsortering.

69
00:03:08,340 --> 00:03:11,941
Så nu går vi tillbaka till frågan,
Upprepa tills swap räknaren är 0.

70
00:03:11,941 --> 00:03:13,690
Tja swap räknaren
är 4, så vi tänker

71
00:03:13,690 --> 00:03:15,410
att fortsätta att upprepa denna process igen.

72
00:03:15,410 --> 00:03:19,180
>> Vi kommer att återställa swap räknaren
till 0, och titta på varje intilliggande par.

73
00:03:19,180 --> 00:03:21,890
Så vi börjar med två och 1-- de är
i ordning, så vi byta dem

74
00:03:21,890 --> 00:03:23,620
och vi lägger en till swap räknaren.

75
00:03:23,620 --> 00:03:25,490
2 och 3, de är i ordning.

76
00:03:25,490 --> 00:03:27,060
Vi behöver inte göra någonting.

77
00:03:27,060 --> 00:03:28,420
3 och 5 är i ordning.

78
00:03:28,420 --> 00:03:30,150
Vi behöver inte göra något där.

79
00:03:30,150 --> 00:03:32,515
>> 5 och 4, de är ute
av ordning, och så vi

80
00:03:32,515 --> 00:03:35,130
måste byta dem och lägg
1 till swap räknaren.

81
00:03:35,130 --> 00:03:38,880
Och nu har vi flyttat 5,
den näst största elementet,

82
00:03:38,880 --> 00:03:40,920
till slutet av osorterade delen.

83
00:03:40,920 --> 00:03:44,360
Så kan vi nu kallar det
en del av det sorterade partiet.

84
00:03:44,360 --> 00:03:47,180
>> Nu är du tittar på den
skärm och förmodligen kan berätta,

85
00:03:47,180 --> 00:03:50,130
som kan jag, att uppsättningen
sorteras just nu.

86
00:03:50,130 --> 00:03:51,820
Men vi kan inte bevisa det ännu.

87
00:03:51,820 --> 00:03:54,359
Vi har inte en garanti
att det är för sortering.

88
00:03:54,359 --> 00:03:56,900
Men det är där swap
disk kommer att träda i funktion.

89
00:03:56,900 --> 00:03:59,060
>> Så vi har avslutat ett pass.

90
00:03:59,060 --> 00:04:00,357
Swapräknaren är 2.

91
00:04:00,357 --> 00:04:02,190
Så vi kommer att upprepa
denna process igen,

92
00:04:02,190 --> 00:04:04,290
Upprepa tills swap räknaren är 0.

93
00:04:04,290 --> 00:04:05,550
Återställ swap mot 0.

94
00:04:05,550 --> 00:04:06,820
Så vi kommer att återställa den.

95
00:04:06,820 --> 00:04:09,810
>> Nu tittar på varje angränsande par.

96
00:04:09,810 --> 00:04:11,880
Det är i sin ordning, 1 och 2.

97
00:04:11,880 --> 00:04:13,590
2 och 3 är i ordning.

98
00:04:13,590 --> 00:04:15,010
3 och 4 är i ordning.

99
00:04:15,010 --> 00:04:19,250
Så på denna punkt, märker vi har slutfört
titta på varje angränsande par,

100
00:04:19,250 --> 00:04:22,530
men swap räknaren är fortfarande 0.

101
00:04:22,530 --> 00:04:25,520
>> Om vi ​​inte behöver växla
några element, då de

102
00:04:25,520 --> 00:04:28,340
måste vara i ordning, genom
kraft av denna process.

103
00:04:28,340 --> 00:04:32,000
Och så en effektivitet av olika slag,
att vi datavetare älskar,

104
00:04:32,000 --> 00:04:35,560
är vi nu deklarera
hela gruppen måste

105
00:04:35,560 --> 00:04:38,160
sorteras, eftersom vi inte
måste byta några delar.

106
00:04:38,160 --> 00:04:40,380
Det är ganska trevligt.

107
00:04:40,380 --> 00:04:43,260
>> Så vad är det värsta fallet
scenario med bubbelsortering?

108
00:04:43,260 --> 00:04:46,240
I värsta fall arrayen är
i helt omvänd ordning,

109
00:04:46,240 --> 00:04:49,870
och så vi måste bubbla varje
av de stora elementen alla

110
00:04:49,870 --> 00:04:51,780
vägen över arrayen.

111
00:04:51,780 --> 00:04:55,350
Och vi effektivt även behöva
bubbla alla de små elementen tillbaka

112
00:04:55,350 --> 00:04:57,050
hela vägen över arrayen, också.

113
00:04:57,050 --> 00:05:01,950
Så vart och ett av de n elementen måste flytta
över alla de andra n element.

114
00:05:01,950 --> 00:05:04,102
Så det är det värsta scenariot.

115
00:05:04,102 --> 00:05:05,810
I bästa fall
scenario är dock detta

116
00:05:05,810 --> 00:05:07,880
skiljer sig något från val slag.

117
00:05:07,880 --> 00:05:10,040
Matrisen är redan
sorterade när vi går in.

118
00:05:10,040 --> 00:05:12,550
Vi behöver inte göra några
swappar på det första passet.

119
00:05:12,550 --> 00:05:14,940
Så vi kanske måste se
på färre element, eller hur?

120
00:05:14,940 --> 00:05:18,580
Vi behöver inte upprepa denna
bearbeta ett antal gånger under.

121
00:05:18,580 --> 00:05:19,540
>> Så vad betyder det?

122
00:05:19,540 --> 00:05:22,390
Så vad är det värsta scenariot
för bubbelsortering, och vad som är

123
00:05:22,390 --> 00:05:25,330
det bästa scenariot för bubbelsortering?

124
00:05:25,330 --> 00:05:27,770
Har du gissa det?

125
00:05:27,770 --> 00:05:32,420
I värsta fall måste man iterera
i alla de n elementen n gånger.

126
00:05:32,420 --> 00:05:34,220
Så det värsta fallet är n i kvadrat.

127
00:05:34,220 --> 00:05:36,550
>> Om arrayen är perfekt
sorterade men bara du

128
00:05:36,550 --> 00:05:38,580
måste titta på varje
av elementen gång.

129
00:05:38,580 --> 00:05:42,670
Och om växlingsräknaren fortfarande är 0,
du kan säga detta arrayen sorteras.

130
00:05:42,670 --> 00:05:45,780
Och så i bästa fall, är detta
faktiskt bättre än val

131
00:05:45,780 --> 00:05:49,230
sort-- det är omega n.

132
00:05:49,230 --> 00:05:50,270
>> Jag är Doug Lloyd.

133
00:05:50,270 --> 00:05:52,140
Detta är CS50.

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