1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [Mull sorteerida]

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP Harvardi Ülikool]

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

4
00:00:08,000 --> 00:00:11,730
Mull sorteerida on näide sortimise algoritm -

5
00:00:11,730 --> 00:00:14,460
see tähendab, et kord sorteerimine komplekt elemendid

6
00:00:14,460 --> 00:00:15,840
kasvavas või kahanevas järjekorras.

7
00:00:15,840 --> 00:00:18,710
Näiteks kui sa tahad sortida massiivi koosneb numbrid

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], nõuetekohase rakendamise mull sorteerida Jõutakse

9
00:00:23,060 --> 00:00:26,260
sorteeritud massiiv [2, 3, 5, 9] tõusvas järjekorras.

10
00:00:26,260 --> 00:00:28,850
Nüüd ma lähen selgitada pseudokoodi kuidas algoritm töötab.

11
00:00:28,850 --> 00:00:34,000
>> Oletame, et me sorteerimine nimekiri 5 täisarvud - 3, 2, 9, 6, ja 5.

12
00:00:34,000 --> 00:00:37,650
Algoritm algab vaadates kaks esimest elementi, 3 ja 2,

13
00:00:37,650 --> 00:00:40,850
ja kontrollida, kas nad on rikkis üksteise suhtes.

14
00:00:40,850 --> 00:00:43,150
Nad on - 3 on suurem kui 2.

15
00:00:43,150 --> 00:00:45,190
Et olla tõusvas järjekorras, peaksid nad olema teistpidi.

16
00:00:45,190 --> 00:00:46,610
Niisiis, me vahetada neid.

17
00:00:46,610 --> 00:00:49,760
Nüüd nimekiri näeb välja selline: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Järgmiseks vaatame teist ja kolmandat elementi, 3 ja 9.

19
00:00:52,450 --> 00:00:55,770
Nad on õiges järjekorras üksteise suhtes.

20
00:00:55,770 --> 00:00:58,800
See on, 3 on alla 9 nii algoritm ei vahetada neid.

21
00:00:58,800 --> 00:01:01,900
Järgmiseks vaatame 9 ja 6. Nad on rikkis.

22
00:01:01,900 --> 00:01:04,260
>> Niisiis, me peame vahetada neid, sest 9 on suurem kui 6.

23
00:01:04,260 --> 00:01:08,840
Lõpuks vaatleme viimase kahe täisarvu, 9 ja 5..

24
00:01:08,840 --> 00:01:10,850
Nad on rikkis, nii et nad tuleb vahetada.

25
00:01:10,850 --> 00:01:13,360
Pärast esimest täielik läbivad nimekirja,

26
00:01:13,360 --> 00:01:17,140
see näeb välja selline: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Pole paha. See on peaaegu järjestatud.

28
00:01:19,690 --> 00:01:22,450
Aga meil on vaja joosta nimekirja uuesti, et saan seda täiesti sorteerida.

29
00:01:22,450 --> 00:01:29,250
Kaks on alla 3, nii et me ei vahetada neid.

30
00:01:29,250 --> 00:01:31,700
>> Kolm on väiksem kui 6, nii et me ei vahetada neid.

31
00:01:31,700 --> 00:01:35,500
Kuus on suurem kui 5. Me vahetasid.

32
00:01:35,500 --> 00:01:38,460
Kuus on alla 9. Me ei vaheta.

33
00:01:38,460 --> 00:01:42,170
Pärast teist läbida, see näeb välja selline: [2, 3, 5, 6, 9]. Perfect.

34
00:01:42,170 --> 00:01:44,680
Nüüd saab kirjutada seda pseudokoodi.

35
00:01:44,680 --> 00:01:48,450
Põhimõtteliselt iga element nimekirjas, me peame vaatama seda

36
00:01:48,450 --> 00:01:50,060
ja osa otse oma õigust.

37
00:01:50,060 --> 00:01:53,420
Kui nad on rikkis üksteise suhtes - see tähendab, kui element vasakul

38
00:01:53,420 --> 00:01:56,810
on suurem kui üks paremal - peaksime swap kaks elementi.

39
00:01:56,810 --> 00:02:01,270
>> Me teeme seda iga element nimekiri, ja me oleme teinud ühe läbida.

40
00:02:01,270 --> 00:02:05,160
Nüüd lihtsalt pead tegema läbipääs piisavalt korda, et tagada nimekirja

41
00:02:05,160 --> 00:02:06,480
täielikult, õigesti järjestatud.

42
00:02:06,480 --> 00:02:08,889
Aga mitu korda me peame läbima nimekirja

43
00:02:08,889 --> 00:02:10,400
garanteerida, et me oleme valmis?

44
00:02:10,400 --> 00:02:14,730
Noh, halvimal juhul on see, kui meil on täiesti tagurpidi nimekirja.

45
00:02:14,730 --> 00:02:17,840
Siis kulub mitu läbivad läbi ekspordi hulk on võrdne

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

47
00:02:19,730 --> 00:02:24,720
Kui see ei ole mõtet intuitiivselt, mõtlevad lihtne juhtum - nimekiri [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> See saab olla üks läbipääs sorteerida õigesti.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - halvimal juhul on see, et 3 elementi järjestatud tahapoole,

50
00:02:33,060 --> 00:02:34,830
see saab võtta 2 korduste omamoodi.

51
00:02:34,830 --> 00:02:37,980
Pärast ühe iteratsiooni, see [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Teine saagikus sorteeritud massiiv [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Nii et sa tead, sa ei pea minema läbi massiivi üldiselt

54
00:02:43,350 --> 00:02:46,790
rohkem kui n-1 korda, kus n on elementide arv massiivis.

55
00:02:47,090 --> 00:02:50,470
Seda nimetatakse mull sorteerida, sest suurim elemendid kipuvad "mull-up"

56
00:02:50,470 --> 00:02:51,950
paremale päris kiiresti.

57
00:02:51,950 --> 00:02:53,980
Tegelikult on see algoritm on väga huvitav käitumine.

58
00:02:53,980 --> 00:02:57,410
>> Pärast m korduste kaudu kogu antennide massiivi,

59
00:02:57,410 --> 00:02:59,000
parempoolsem m elemendid on tagatud

60
00:02:59,000 --> 00:03:01,000
välja sorteerida oma õigesse kohta.

61
00:03:01,000 --> 00:03:02,280
Kui soovite seda ise nägema,

62
00:03:02,280 --> 00:03:05,500
saame proovida seda täiesti tagurpidi nimekiri [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Pärast ühte läbivad kogu nimekirja,

64
00:03:08,220 --> 00:03:09,220
[Heli kirjutamiseks]

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
parempoolsem 9. osa on tema õige koht.

67
00:03:21,250 --> 00:03:24,760
Pärast teist läbipääs, 6 on "mullidena üles", et

68
00:03:24,760 --> 00:03:26,220
2. parempoolsem koht.

69
00:03:26,220 --> 00:03:28,840
Kahest elemendist paremal - 6 ja 9 - on nende õiged kohad

70
00:03:28,840 --> 00:03:30,580
Pärast kahte esimest liigu läbi ekspordi.

71
00:03:30,580 --> 00:03:32,590
>> Niisiis, kuidas me saame kasutada seda optimeerida algoritm?

72
00:03:32,590 --> 00:03:34,850
Noh, pärast ühe iteratsiooni kaudu massiivi

73
00:03:34,850 --> 00:03:37,690
me tegelikult ei vaja, et kontrollida parempoolsem osa

74
00:03:37,690 --> 00:03:39,200
sest me teame, see on järjestatud.

75
00:03:39,200 --> 00:03:43,050
Pärast kaks iteratsiooni, mida me teame kindlasti parempoolsem kaks elementi on olemas.

76
00:03:43,050 --> 00:03:48,260
Niisiis, üldiselt pärast k korduste kaudu kogu massiiv,

77
00:03:48,260 --> 00:03:51,550
kontrollides viimase k elementi on ülearune, sest me teame

78
00:03:51,550 --> 00:03:52,360
nad õiges kohas juba.

79
00:03:52,360 --> 00:03:54,870
>> Seega, kui olete sorteerimine massiivi n elementi,

80
00:03:54,870 --> 00:03:57,870
aasta esimese iteratsiooni - you'll on sorteerida kõik elemendid - esimene n-0.

81
00:03:57,870 --> 00:04:04,170
Teisel iteratsiooni, sa pead vaatama kõiki elemente, kuid viimasel -

82
00:04:04,170 --> 00:04:07,090
esimese n-1.

83
00:04:07,090 --> 00:04:10,520
Teine optimeerimine võib olla kontrollida, kas nimekiri on juba järjestatud

84
00:04:10,520 --> 00:04:11,710
pärast iga iteratsiooni.

85
00:04:11,710 --> 00:04:13,900
Kui see on juba järjestatud, meil ei ole vaja teha enam kordustes

86
00:04:13,900 --> 00:04:15,310
nimekiri läbi.

87
00:04:15,310 --> 00:04:16,220
Kuidas me saame seda teha?

88
00:04:16,220 --> 00:04:19,360
Noh, kui me ei tee vahetustehingute läbipääs nimekirja,

89
00:04:19,360 --> 00:04:22,350
on selge, et loetelu on juba järjestatud, sest me ei vaheta midagi.

90
00:04:22,350 --> 00:04:24,160
Nii et me kindlasti ei pea sortida jälle.

91
00:04:24,160 --> 00:04:27,960
>> Äkki saab initsialiseerida lipu muutuja nimega "sorteerimata", et

92
00:04:27,960 --> 00:04:30,990
vale ja muuda see tõsi, kui teil on vahetada mis tahes elementide

93
00:04:30,990 --> 00:04:32,290
ühe iteratsiooni kaudu massiivi.

94
00:04:32,290 --> 00:04:35,350
Või samamoodi teha loenduri loendama, kui paljud vahetustehingud teete

95
00:04:35,350 --> 00:04:37,040
igal konkreetsel iteratsiooni.

96
00:04:37,040 --> 00:04:40,040
Lõpus iteratsiooni, kui te ei vaheta tahes osades,

97
00:04:40,040 --> 00:04:41,780
sa tead, et loend on juba sorteeritud ja sa oled teinud.

98
00:04:41,780 --> 00:04:44,090
Mull sorteerida, nagu ka teised sorteerimise algoritme, võib olla

99
00:04:44,090 --> 00:04:46,960
Tweaked tööle ühtki asjaolu, mis on tellimise meetodit.

100
00:04:46,960 --> 00:04:50,610
>> See tähendab, et antud kaks elementi teil on võimalus öelda kui esimene

101
00:04:50,610 --> 00:04:53,770
on üle, on võrdne või väiksem kui teine.

102
00:04:53,770 --> 00:04:56,870
Näiteks võid sorteerida tähestiku öeldes

103
00:04:56,870 --> 00:05:00,520
et a <b, b <c, jne

104
00:05:00,520 --> 00:05:03,830
Või võite sortida nädalapäevade kus pühapäeval on vähem kui esmaspäev

105
00:05:03,830 --> 00:05:05,110
mis on vähem kui teisipäeval.

106
00:05:05,110 --> 00:05:09,630
>> Bubble Sort ei ole sugugi väga tõhus või kiire sortimise algoritm.

107
00:05:09,630 --> 00:05:12,370
Selle halvima runtime on Big O n ²

108
00:05:12,370 --> 00:05:14,810
sest sa pead tegema n iteratsiooni kaudu nimekirja

109
00:05:14,810 --> 00:05:18,430
kontrollides kõik n elementi iga läbipääs, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
See läbijooksuaeg tähendab, et kui mitu elementi sa sorteerimine suureneb,

111
00:05:22,730 --> 00:05:24,330
läbijooksuaeg suurendab quadratically.

112
00:05:24,330 --> 00:05:27,330
>> Aga kui efektiivsust ei ole suur mure oma programmi

113
00:05:27,330 --> 00:05:29,550
või kui sa oled ainult sorteerimine vähe elemente,

114
00:05:29,550 --> 00:05:31,660
te võite leida mull sorteerida kasulik, sest

115
00:05:31,660 --> 00:05:33,360
see on üks lihtsamaid sorteerimine algoritme mõista

116
00:05:33,360 --> 00:05:34,250
ja kood.

117
00:05:34,250 --> 00:05:37,270
See on ka suurepärane võimalus saada kogemusi tõlkimise teoreetiline

118
00:05:37,270 --> 00:05:40,220
algoritm arvesse tegelikku toimimist kood.

119
00:05:40,220 --> 00:05:43,000
Noh, see on mull sorteerida teile. Täname vaadates.

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