1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [Bubble Raða]

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

3
00:00:04,560 --> 00:00:07,500
[ÞETTA ER CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Bubble tagi er dæmi um flokkun reiknirit -

5
00:00:11,730 --> 00:00:14,460
það er aðferð til að flokka safn af þáttum í

6
00:00:14,460 --> 00:00:15,840
hækkandi eða lækkandi röð.

7
00:00:15,840 --> 00:00:18,710
Til dæmis, ef þú vildir að raða fylki sem samanstendur af fjölda

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], rétta framkvæmd Raða Bubble myndi skila

9
00:00:23,060 --> 00:00:26,260
raðað array [2, 3, 5, 9] í hækkandi röð.

10
00:00:26,260 --> 00:00:28,850
Nú ætla ég að útskýra í sauðakóðanum hvernig reiknirit virkar.

11
00:00:28,850 --> 00:00:34,000
>> Við skulum segja að við erum að flokka lista yfir 5 heiltölur - 3, 2, 9, 6, og 5.

12
00:00:34,000 --> 00:00:37,650
Reiknirit hefst með því að horfa á fyrstu tvo þætti, 3 og 2,

13
00:00:37,650 --> 00:00:40,850
og athuga hvort þeir eru út af röð miðað við hvert annað.

14
00:00:40,850 --> 00:00:43,150
Þeir eru - 3 um meira en 2.

15
00:00:43,150 --> 00:00:45,190
Til að vera í hækkandi röð, ættu þeir að vera á hinn veginn.

16
00:00:45,190 --> 00:00:46,610
Svo skipta við þá.

17
00:00:46,610 --> 00:00:49,760
Nú lítur listinn svona út: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Næst skaltu líta við á öðrum og þriðja þætti, 3 og 9.

19
00:00:52,450 --> 00:00:55,770
Þeir eru í réttri röð miðað við hvert annað.

20
00:00:55,770 --> 00:00:58,800
Það er, 3 er minna en 9 þannig að reiknirit ekki skipta þeim.

21
00:00:58,800 --> 00:01:01,900
Næst skaltu líta við á 9 og 6. Þeir eru út af röð.

22
00:01:01,900 --> 00:01:04,260
>> Svo þurfum við að skipta á þeim vegna þess að 9 er meiri en 6.

23
00:01:04,260 --> 00:01:08,840
Loksins, horfum við á síðustu tvær heiltölur, 9 og 5.

24
00:01:08,840 --> 00:01:10,850
Þeir eru út af röð, svo þeir verða að vera skipti.

25
00:01:10,850 --> 00:01:13,360
Eftir fyrsta heila umferð í gegnum listann,

26
00:01:13,360 --> 00:01:17,140
það lítur svona út: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Ekki slæmt. Það er nánast raðað.

28
00:01:19,690 --> 00:01:22,450
En við þurfum að keyra í gegnum listann aftur til að fá það raðað alveg.

29
00:01:22,450 --> 00:01:29,250
Two er minna en 3, svo að við skipta þeim ekki.

30
00:01:29,250 --> 00:01:31,700
>> Þrír er minna en 6, svo að við skipta þeim ekki.

31
00:01:31,700 --> 00:01:35,500
Sex er meiri en 5. Við skipti.

32
00:01:35,500 --> 00:01:38,460
Sex er minna en 9. Við skipti ekki.

33
00:01:38,460 --> 00:01:42,170
Eftir að seinni umferð í gegnum, það útlit eins og this: [2, 3, 5, 6, 9]. Perfect.

34
00:01:42,170 --> 00:01:44,680
Nú, við skulum skrifa það í sauðakóðanum.

35
00:01:44,680 --> 00:01:48,450
Í grundvallaratriðum, fyrir hvert frumefni á listanum, þurfum við að líta á það

36
00:01:48,450 --> 00:01:50,060
og þáttur beint að sér.

37
00:01:50,060 --> 00:01:53,420
Ef þeir eru út af röð miðað við hvert annað - það er, ef þátturinn á vinstri

38
00:01:53,420 --> 00:01:56,810
er meiri en einn á rétt - við ættum að skipta um tvo hluti.

39
00:01:56,810 --> 00:02:01,270
>> Við gerum þetta fyrir hvert frumefni á listanum, og við höfum gert einn fara í gegnum.

40
00:02:01,270 --> 00:02:05,160
Nú verðum við bara að gera framhjá-í gegnum nógu oft til að tryggja lista

41
00:02:05,160 --> 00:02:06,480
er fullkomlega, rétt raðað.

42
00:02:06,480 --> 00:02:08,889
En hversu oft eigum við að fara í gegnum listann til

43
00:02:08,889 --> 00:02:10,400
tryggja að við erum að gera?

44
00:02:10,400 --> 00:02:14,730
Jæja, versta er ef við höfum alveg aftur á bak lista.

45
00:02:14,730 --> 00:02:17,840
Þá tekur það fjölda líða throughs jafn fjölda

46
00:02:17,840 --> 00:02:19,730
af þætti N-1.

47
00:02:19,730 --> 00:02:24,720
Ef þetta er ekki skynsamleg innsær, hugsa um einfalt mál - listi [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Þetta er að fara að taka einn fara í gegnum til að raða rétt.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Í versta falli er þessi með 3 þáttum raðað aftur,

50
00:02:33,060 --> 00:02:34,830
það er að fara að taka 2 endurtekningar til að flokka.

51
00:02:34,830 --> 00:02:37,980
Eftir einn endurtekning, það er [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Annað fæst raðað array [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Svo þú veist að þú aldrei þurft að fara í gegnum fjölda, almennt,

54
00:02:43,350 --> 00:02:46,790
meira en n-1 sinnum, þar sem n er fjöldi staka í fylkinu.

55
00:02:47,090 --> 00:02:50,470
Það heitir Bubble Raða vegna stærstu þættir hafa tilhneigingu til að "kúla-upp '

56
00:02:50,470 --> 00:02:51,950
til hægri frekar hratt.

57
00:02:51,950 --> 00:02:53,980
Í raun, þetta reiknirit er mjög áhugavert hegðun.

58
00:02:53,980 --> 00:02:57,410
>> Eftir m endurtekningar gegnum allt fylki,

59
00:02:57,410 --> 00:02:59,000
á rightmost m þættir eru tryggð

60
00:02:59,000 --> 00:03:01,000
að vera flokkaður í rétta stað þeirra.

61
00:03:01,000 --> 00:03:02,280
Ef þú vilt sjá þetta fyrir sjálfan þig,

62
00:03:02,280 --> 00:03:05,500
við getum reynt það á alveg afturábak lista [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Eftir eina umferð um allan listann,

64
00:03:08,220 --> 00:03:09,220
[Hljóð skrifa]

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
á rightmost þáttur 9 er í rétta stað.

67
00:03:21,250 --> 00:03:24,760
Eftir seinni framhjá-í gegnum, að 6 verður "bubbled upp 'til

68
00:03:24,760 --> 00:03:26,220
annað rightmost stað.

69
00:03:26,220 --> 00:03:28,840
Þeir tveir þættir á hægri - 6 og 9 - mun vera í réttum stöðum sínum

70
00:03:28,840 --> 00:03:30,580
eftir fyrstu tveimur framhjá throughs.

71
00:03:30,580 --> 00:03:32,590
>> Svo, hvernig getum við notað þetta til að hámarka reiknirit?

72
00:03:32,590 --> 00:03:34,850
Jæja, eftir einn endurtekning gegnum fylki

73
00:03:34,850 --> 00:03:37,690
við gerum ekki raunverulega þörf til að athuga rightmost þáttur

74
00:03:37,690 --> 00:03:39,200
vegna þess að við vitum að það er flokkað.

75
00:03:39,200 --> 00:03:43,050
Eftir tvær endurtekningar, vitum við að tryggja að rightmost tveir þættir eru á sínum stað.

76
00:03:43,050 --> 00:03:48,260
Svo almennt, eftir endurtekningar k með fullri array,

77
00:03:48,260 --> 00:03:51,550
haka við síðustu þætti K er óþarfi þar sem við vitum

78
00:03:51,550 --> 00:03:52,360
þeir eru á réttan stað þegar.

79
00:03:52,360 --> 00:03:54,870
>> Svo ef þú ert að flokka fjölda n þáttum,

80
00:03:54,870 --> 00:03:57,870
á fyrsta endurtekning - you'll að raða öllum þeim þáttum - fyrstu n-0.

81
00:03:57,870 --> 00:04:04,170
Á seinni endurtekning, þarftu að líta á alla þá þætti, en síðasta -

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

83
00:04:07,090 --> 00:04:10,520
Annar hagræðingu gæti verið að athuga hvort listinn er þegar raðað

84
00:04:10,520 --> 00:04:11,710
eftir hverja ítrun.

85
00:04:11,710 --> 00:04:13,900
Ef það er þegar raðað, þurfum við ekki að gera eitthvað meira endurtekningar

86
00:04:13,900 --> 00:04:15,310
gegnum listann.

87
00:04:15,310 --> 00:04:16,220
Hvernig getum við gert þetta?

88
00:04:16,220 --> 00:04:19,360
Jæja, ef við ekki gera neinar skiptasamninga á að fara í gegnum á listanum,

89
00:04:19,360 --> 00:04:22,350
það er ljóst að listinn var þegar raðað vegna þess að við ekki skipta neitt.

90
00:04:22,350 --> 00:04:24,160
Þannig að við örugglega ekki að raða aftur.

91
00:04:24,160 --> 00:04:27,960
>> Kannski þú gætir frumstilla fána breytu sem heitir "ekki raðað 'til

92
00:04:27,960 --> 00:04:30,990
falskar og breyta því að sanna ef þú ert að skipta á þætti á

93
00:04:30,990 --> 00:04:32,290
einn endurtekning gegnum fylki.

94
00:04:32,290 --> 00:04:35,350
Eða álíka, gera teljara til að telja hversu margir samningar sem þú gerir

95
00:04:35,350 --> 00:04:37,040
á hverjum endurtekning.

96
00:04:37,040 --> 00:04:40,040
Í lok sem endurtekning, ef þú did ekki skipta einhverju af þeim þáttum,

97
00:04:40,040 --> 00:04:41,780
þú veist að listinn er nú þegar raðað og þú ert búinn.

98
00:04:41,780 --> 00:04:44,090
Bubble Raða, eins og önnur reiknirit flokkun, er hægt að

99
00:04:44,090 --> 00:04:46,960
klip til að vinna fyrir öllum þáttum sem geta haft röðun aðferð.

100
00:04:46,960 --> 00:04:50,610
>> Það er gefið tveimur þáttum þú hafa a vegur til segja ef fyrsta

101
00:04:50,610 --> 00:04:53,770
er stærra en, jafnt eða minna en sekúndu.

102
00:04:53,770 --> 00:04:56,870
Til dæmis, getur þú flokkað bókstafina með því að segja

103
00:04:56,870 --> 00:05:00,520
að a <b, b <c, osfrv

104
00:05:00,520 --> 00:05:03,830
Eða þú gætir raða daga vikunnar þar sem sunnudagur er minna en Mánudagur

105
00:05:03,830 --> 00:05:05,110
sem er minna en þriðjudag.

106
00:05:05,110 --> 00:05:09,630
>> Bubble tagi er alls ekki mjög duglegur og fljótur flokkun reiknirit.

107
00:05:09,630 --> 00:05:12,370
Versta afturkreistingur þess er Big O n ²

108
00:05:12,370 --> 00:05:14,810
vegna þess að þú þarft að gera n endurtekningar gegnum lista

109
00:05:14,810 --> 00:05:18,430
stöðva öll n þætti hvor framhjá-í gegnum, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Þetta hlaupa tími þýðir að eftir því sem fjöldi þátta sem þú ert að flokka eykst

111
00:05:22,730 --> 00:05:24,330
hlaupa tími eykst quadratically.

112
00:05:24,330 --> 00:05:27,330
>> En ef skilvirkni er ekki stórt áhyggjuefni program

113
00:05:27,330 --> 00:05:29,550
eða ef þú ert bara flokka fáeinum þáttum,

114
00:05:29,550 --> 00:05:31,660
þú gætir fundið Bubble Raða gagnlegur því

115
00:05:31,660 --> 00:05:33,360
það er eitt af einföldustu flokkun reiknirit til að skilja

116
00:05:33,360 --> 00:05:34,250
og til að kóða.

117
00:05:34,250 --> 00:05:37,270
Það er líka frábær leið til að fá reynslu af að þýða fræðilega

118
00:05:37,270 --> 00:05:40,220
reiknirit í raun starfsemi kóða.

119
00:05:40,220 --> 00:05:43,000
Jæja, það er kúla Raða fyrir þig. Takk fyrir að horfa.

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