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 University]

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

4
00:00:08,000 --> 00:00:11,730
Boble Sorter er et eksempel på en sortering algoritme -

5
00:00:11,730 --> 00:00:14,460
det vil si en fremgangsmåte for sortering et sett av elementer i

6
00:00:14,460 --> 00:00:15,840
stigende eller synkende rekkefølge.

7
00:00:15,840 --> 00:00:18,710
For eksempel, hvis du ønsket å sortere en rekke bestående av tallene

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], ville en korrekt gjennomføring av Bubble Sorter returnere

9
00:00:23,060 --> 00:00:26,260
sorteres array [2, 3, 5, 9] i stigende rekkefølge.

10
00:00:26,260 --> 00:00:28,850
Nå skal jeg forklare i pseudokode hvordan algoritmen fungerer.

11
00:00:28,850 --> 00:00:34,000
>> La oss si at vi sortering en liste over 5 heltall - 3, 2, 9, 6 og 5.

12
00:00:34,000 --> 00:00:37,650
Algoritmen starter ved å se på de første to elementer, 3 og 2,

13
00:00:37,650 --> 00:00:40,850
og sjekke om de er ute av rekkefølge i forhold til hverandre.

14
00:00:40,850 --> 00:00:43,150
De er - 3 er større enn 2.

15
00:00:43,150 --> 00:00:45,190
Å være i stigende rekkefølge, bør de være den andre veien rundt.

16
00:00:45,190 --> 00:00:46,610
Så bytter vi dem.

17
00:00:46,610 --> 00:00:49,760
Nå er listen ser slik ut: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Deretter ser vi på andre og tredje element, 3 og 9.

19
00:00:52,450 --> 00:00:55,770
De er i riktig rekkefølge i forhold til hverandre.

20
00:00:55,770 --> 00:00:58,800
Som er, er 3 mindre enn 9 så algoritmen ikke bytte dem.

21
00:00:58,800 --> 00:01:01,900
Deretter ser vi på 9 og 6. De er ute av drift.

22
00:01:01,900 --> 00:01:04,260
>> Så må vi bytte dem fordi 9 er større enn 6.

23
00:01:04,260 --> 00:01:08,840
Til slutt ser vi på de siste to heltall, 9 og 5.

24
00:01:08,840 --> 00:01:10,850
De er ute av drift, slik at de må byttes.

25
00:01:10,850 --> 00:01:13,360
Etter den første komplette pass gjennom listen,

26
00:01:13,360 --> 00:01:17,140
det ser ut som dette: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Ikke dårlig. Det er nesten sortert.

28
00:01:19,690 --> 00:01:22,450
Men vi må kjøre gjennom listen igjen for å få det helt sortert.

29
00:01:22,450 --> 00:01:29,250
To er mindre enn 3, så vi ikke bytte dem.

30
00:01:29,250 --> 00:01:31,700
>> Tre er mindre enn 6, så vi ikke bytte dem.

31
00:01:31,700 --> 00:01:35,500
Seks er større enn 5. Vi byttet.

32
00:01:35,500 --> 00:01:38,460
Seks er mindre enn 9. Vi bytter ikke.

33
00:01:38,460 --> 00:01:42,170
Etter den andre passerer gjennom, ser det slik ut: [2, 3, 5, 6, 9]. Perfekt.

34
00:01:42,170 --> 00:01:44,680
Nå, la oss skrive det i pseudokode.

35
00:01:44,680 --> 00:01:48,450
I utgangspunktet, for hvert element i listen, må vi se på det

36
00:01:48,450 --> 00:01:50,060
og elementet direkte til sin rett.

37
00:01:50,060 --> 00:01:53,420
Hvis de er ute av drift i forhold til hverandre - det vil si hvis elementet på venstre

38
00:01:53,420 --> 00:01:56,810
er større enn den på høyre - vi skal bytte de to elementene.

39
00:01:56,810 --> 00:02:01,270
>> Vi gjør dette for hvert element i listen, og vi har gjort en gjennomgående.

40
00:02:01,270 --> 00:02:05,160
Nå er vi bare nødt til å gjøre Gjennomslaget nok ganger for å sikre listen

41
00:02:05,160 --> 00:02:06,480
er fullt, skikkelig sortert.

42
00:02:06,480 --> 00:02:08,889
Men hvor mange ganger må vi gå gjennom listen for å

43
00:02:08,889 --> 00:02:10,400
garantere at vi er ferdige?

44
00:02:10,400 --> 00:02:14,730
Vel, er det verst tenkelige scenario hvis vi har en helt bakover liste.

45
00:02:14,730 --> 00:02:17,840
Så det tar et antall pass-gjennomføringer lik tallet

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

47
00:02:19,730 --> 00:02:24,720
Hvis dette ikke gir mening intuitivt, tenke på en enkel sak - listen [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Dette kommer til å ta en pass-through for å sortere riktig.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Det verste tilfellet er at med 3 elementer sorteres bakover,

50
00:02:33,060 --> 00:02:34,830
det kommer til å ta 2 iterasjoner for å sortere.

51
00:02:34,830 --> 00:02:37,980
Etter en iterasjon, er det [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
De andre utbytter den sorterte matrisen [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Så du vet at du aldri trenger å gå gjennom tabellen, generelt,

54
00:02:43,350 --> 00:02:46,790
mer enn n-1 ganger, der n er antallet elementer i matrisen.

55
00:02:47,090 --> 00:02:50,470
Det kalles Bubble Sorter fordi de største elementene har en tendens til å "boble-up '

56
00:02:50,470 --> 00:02:51,950
til høyre ganske raskt.

57
00:02:51,950 --> 00:02:53,980
Faktisk har denne algoritmen meget interessant atferd.

58
00:02:53,980 --> 00:02:57,410
>> Etter m iterasjoner gjennom hele matrisen,

59
00:02:57,410 --> 00:02:59,000
lengst til høyre m elementene er garantert

60
00:02:59,000 --> 00:03:01,000
skal sorteres i sin riktig sted.

61
00:03:01,000 --> 00:03:02,280
Hvis du ønsker å se dette selv,

62
00:03:02,280 --> 00:03:05,500
Vi kan prøve det på en helt bakover liste [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Etter en passering gjennom hele listen,

64
00:03:08,220 --> 00:03:09,220
[Lyden av skriving]

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
lengst til høyre element 9 er på sin rette plass.

67
00:03:21,250 --> 00:03:24,760
Etter den andre passering, vil 6 har 'boblet opp' til

68
00:03:24,760 --> 00:03:26,220
andre lengst sted.

69
00:03:26,220 --> 00:03:28,840
De to elementene på høyre - 6 og 9 - vil være i deres riktige steder

70
00:03:28,840 --> 00:03:30,580
etter de første to pass-throughs.

71
00:03:30,580 --> 00:03:32,590
>> Så, hvordan kan vi bruke dette til å optimalisere algoritme?

72
00:03:32,590 --> 00:03:34,850
Vel, etter en iterasjon gjennom matrisen

73
00:03:34,850 --> 00:03:37,690
vi ikke egentlig trenger å sjekke lengst element

74
00:03:37,690 --> 00:03:39,200
fordi vi vet at det sortert.

75
00:03:39,200 --> 00:03:43,050
Etter to iterasjoner, vet vi sikkert den høyre to elementene er på plass.

76
00:03:43,050 --> 00:03:48,260
Så, generelt, etter k iterasjoner gjennom en fullstendig matrise,

77
00:03:48,260 --> 00:03:51,550
sjekke de siste k elementer er overflødig siden vi vet

78
00:03:51,550 --> 00:03:52,360
de er på riktig sted allerede.

79
00:03:52,360 --> 00:03:54,870
>> Så hvis du sortering en rekke n elementer,

80
00:03:54,870 --> 00:03:57,870
på den første iterasjon - du må sortere alle elementene - de første n-0.

81
00:03:57,870 --> 00:04:04,170
På den andre iterasjon, må du se på alle elementene, men den siste -

82
00:04:04,170 --> 00:04:07,090
de første n-1.

83
00:04:07,090 --> 00:04:10,520
En annen optimalisering kan være å sjekke om listen er allerede sortert

84
00:04:10,520 --> 00:04:11,710
etter hver iterasjon.

85
00:04:11,710 --> 00:04:13,900
Hvis det er allerede sortert, trenger vi ikke å gjøre noen flere iterasjoner

86
00:04:13,900 --> 00:04:15,310
gjennom listen.

87
00:04:15,310 --> 00:04:16,220
Hvordan kan vi gjøre dette?

88
00:04:16,220 --> 00:04:19,360
Vel, hvis vi ikke gjør noen bytter på en pass-through av listen,

89
00:04:19,360 --> 00:04:22,350
det er klart at listen var allerede sortert fordi vi ikke bytte noe.

90
00:04:22,350 --> 00:04:24,160
Så vi definitivt ikke trenger å sortere igjen.

91
00:04:24,160 --> 00:04:27,960
>> Kanskje du kunne initialisere et flagg variabel kalt "ikke sortert 'til

92
00:04:27,960 --> 00:04:30,990
falsk og endre den til true hvis du må bytte noen elementer på

93
00:04:30,990 --> 00:04:32,290
en iterasjon gjennom matrisen.

94
00:04:32,290 --> 00:04:35,350
Eller tilsvarende, må en teller til å telle hvor mange swaps du gjør

95
00:04:35,350 --> 00:04:37,040
på en gitt iterasjon.

96
00:04:37,040 --> 00:04:40,040
På slutten av en iterasjon, hvis du ikke bytte noen av elementene,

97
00:04:40,040 --> 00:04:41,780
du vet listen er allerede sortert, og du er ferdig.

98
00:04:41,780 --> 00:04:44,090
Bubble Sorter, som andre sortering algoritmer, kan være

99
00:04:44,090 --> 00:04:46,960
forskjøvet til å jobbe for noen elementer som har en bestilling metode.

100
00:04:46,960 --> 00:04:50,610
>> Som er gitt to elementer du har en måte å si om den første

101
00:04:50,610 --> 00:04:53,770
er større enn, lik eller mindre enn den andre.

102
00:04:53,770 --> 00:04:56,870
For eksempel kan du sortere bokstavene i alfabetet ved å si

103
00:04:56,870 --> 00:05:00,520
at en <b, b <c, osv.

104
00:05:00,520 --> 00:05:03,830
Eller du kan sortere dager i uken hvor søndag er mindre enn mandag

105
00:05:03,830 --> 00:05:05,110
som er mindre enn tirsdag.

106
00:05:05,110 --> 00:05:09,630
>> Bubble Sorter er på ingen måte en svært effektiv eller rask sortering algoritme.

107
00:05:09,630 --> 00:05:12,370
Sitt verste-fall runtime er Big O n ²

108
00:05:12,370 --> 00:05:14,810
fordi du har å gjøre n iterasjoner gjennom en liste

109
00:05:14,810 --> 00:05:18,430
sjekke alle n elementer hver passering, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Dette driftstid betyr at du som antall elementer du sortere øker,

111
00:05:22,730 --> 00:05:24,330
kjøretiden øker kvadratisk.

112
00:05:24,330 --> 00:05:27,330
>> Men hvis effektivitet er ikke et stort problem for programmet

113
00:05:27,330 --> 00:05:29,550
eller hvis du bare sortere et lite antall elementer,

114
00:05:29,550 --> 00:05:31,660
du kan finne Bubble Sorter nyttig fordi

115
00:05:31,660 --> 00:05:33,360
det er en av de enkleste sortering algoritmer for å forstå

116
00:05:33,360 --> 00:05:34,250
og å kode.

117
00:05:34,250 --> 00:05:37,270
Det er også en fin måte å få erfaring med å oversette en teoretisk

118
00:05:37,270 --> 00:05:40,220
algoritmen i selve fungerende kode.

119
00:05:40,220 --> 00:05:43,000
Vel, det er Bubble Sorter for deg. Takk for å se.

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