1
00:00:00,000 --> 00:00:03,360
>> [Muusika mängib]

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

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Okei, nii et
mull sorteerida on algoritmi

4
00:00:06,730 --> 00:00:08,730
saate sortida elementide kogum.

5
00:00:08,730 --> 00:00:10,850
Võtame vaatame, kuidas see toimib.

6
00:00:10,850 --> 00:00:13,240
>> Nii põhiidee
mull sorteerida on see.

7
00:00:13,240 --> 00:00:17,340
Me üldiselt tahavad liikuda kõrgema
väärtustatud elemendid üldiselt õige,

8
00:00:17,340 --> 00:00:20,340
ja alandada hinnatud elemendid üldiselt
vasakule, nagu me ootaks.

9
00:00:20,340 --> 00:00:23,256
Me soovime, et väiksem asju olla
Alguses ja kõrgema asju

10
00:00:23,256 --> 00:00:24,970
olema lõpus.

11
00:00:24,970 --> 00:00:26,130
>> Kuidas me seda teeme?

12
00:00:26,130 --> 00:00:28,040
Noh pseudokoodi koodi
võib öelda, olgem

13
00:00:28,040 --> 00:00:30,320
määrata swap vastuollu nullist väärtus.

14
00:00:30,320 --> 00:00:32,570
Me näeme, miks me seda teeme teise.

15
00:00:32,570 --> 00:00:36,090
Ja siis me kordame järgmist
protsessi, kuni swap counter on 0,

16
00:00:36,090 --> 00:00:39,910
või kuni me ei tee vahetustehingud üldse.

17
00:00:39,910 --> 00:00:43,170
>> Taasta swap vastuollu
0, kui see ei ole juba 0.

18
00:00:43,170 --> 00:00:46,420
Siis vaadata igal
kõrvutistest elemente.

19
00:00:46,420 --> 00:00:49,550
Kui need kaks tegurit on
mitte selleks, vahetada neid,

20
00:00:49,550 --> 00:00:51,620
ja lisatakse 1 swap counter.

21
00:00:51,620 --> 00:00:53,870
Kui sa mõtled
seda enne visualiseerida seda,

22
00:00:53,870 --> 00:00:57,471
märgata, et see liigub madalama
väärtustatud elemendid vasakul

23
00:00:57,471 --> 00:01:00,720
ja väärtuslikumateks elemendid paremal,
efektiivselt seda, mida me tahame teha,

24
00:01:00,720 --> 00:01:03,940
mis on liikuda nende rühmade
elementide niimoodi.

25
00:01:03,940 --> 00:01:07,035
Olgem visualiseerida, kuidas seda
võiks vaadata kasutades meie massiivi

26
00:01:07,035 --> 00:01:10,504
et me testimiseks kasutatud
neid algoritme.

27
00:01:10,504 --> 00:01:13,420
Meil on sorteerimata massiivi siin jälle,
tähistatud kõik elemendid

28
00:01:13,420 --> 00:01:14,840
on punane.

29
00:01:14,840 --> 00:01:17,970
Ja ma pöörasin oma swap counter
nonzero väärtus.

30
00:01:17,970 --> 00:01:20,610
Ma suvaliselt valisid
negatiivne 1-- see ei ole 0.

31
00:01:20,610 --> 00:01:23,840
Me tahame, et korrata seda protsessi
kuni swap counter on 0.

32
00:01:23,840 --> 00:01:26,540
See on põhjus, miks ma panen oma swap
vastuollu mõne nullist väärtus,

33
00:01:26,540 --> 00:01:29,400
sest vastasel korral
swap counter oleks 0.

34
00:01:29,400 --> 00:01:31,610
Me isegi ei hakata
protsessi algoritmi.

35
00:01:31,610 --> 00:01:33,610
Nii jälle sammud are--
reset swap counter

36
00:01:33,610 --> 00:01:37,900
0, siis vaatame iga külgnevate
paar, ja kui nad on rikkis,

37
00:01:37,900 --> 00:01:40,514
vahetada neid ja lisada 1
konverteerimist counter.

38
00:01:40,514 --> 00:01:41,680
Nii alustagem seda protsessi.

39
00:01:41,680 --> 00:01:44,430
Nii et esimene asi, mida me teeme on
seadsime swap vastuollu 0,

40
00:01:44,430 --> 00:01:46,660
ja siis hakkame otsima
igal kõrvutistest.

41
00:01:46,660 --> 00:01:49,140
>> Nii me esimest korda hakata otsima 5 ja 2.

42
00:01:49,140 --> 00:01:52,410
Me näeme, et nad on välja
tellida ja nii me vahetada neid.

43
00:01:52,410 --> 00:01:53,830
Ja lisame 1 konverteerimist counter.

44
00:01:53,830 --> 00:01:57,860
Nüüd meie swap counter on 1,
ja 2 ja 5 on sisse lülitatud.

45
00:01:57,860 --> 00:01:59,370
Nüüd korrake protsessi uuesti.

46
00:01:59,370 --> 00:02:03,540
>> Me vaatame järgmise kõrvutistest,
5 ja 1-- nad ka rikkis,

47
00:02:03,540 --> 00:02:06,960
nii et me vahetada neid ja lisada
1 konverteerimist counter.

48
00:02:06,960 --> 00:02:08,900
Siis vaatame 5 ja 3.

49
00:02:08,900 --> 00:02:13,830
Nad on rikkis, nii et me vahetada
neid ja lisame 1 konverteerimist counter.

50
00:02:13,830 --> 00:02:15,550
Siis vaatame 5 ja 6.

51
00:02:15,550 --> 00:02:18,630
Nad on selleks, et me ei ole tegelikult
vaja vahetada midagi seekord.

52
00:02:18,630 --> 00:02:20,250
Siis vaatame 6 ja 4.

53
00:02:20,250 --> 00:02:24,920
Nad on ka korrast ära, nii et me vahetada
neid ja lisame 1 konverteerimist counter.

54
00:02:24,920 --> 00:02:26,230
>> Nüüd pane tähele, mis juhtus.

55
00:02:26,230 --> 00:02:29,514
Me oleme liikunud 6 kogu tee lõpuni.

56
00:02:29,514 --> 00:02:32,180
Nii valikut omamoodi, kui olete
näha, et video, mida me tegime oli

57
00:02:32,180 --> 00:02:35,290
oleme jõudnud liigutades
Väikseim elemendid hoone

58
00:02:35,290 --> 00:02:39,640
sorteeritud massiiv peamiselt
vasakult paremale, väiksemast ja lõpetades suuremaga.

59
00:02:39,640 --> 00:02:43,200
Juhul mull sorteerida, kui me oleme
pärast seda eriti algoritm,

60
00:02:43,200 --> 00:02:46,720
me tegelikult läheb ehitama
sorteeritud massiivi õigus

61
00:02:46,720 --> 00:02:49,100
vasakule, suuremast väiksema.

62
00:02:49,100 --> 00:02:53,840
Oleme efektiivselt mullidena 6
suurima väärtuse, kõik viis kuni lõpuni.

63
00:02:53,840 --> 00:02:56,165
>> Ja nii me nüüd tunnistada
et mis on järjestatud,

64
00:02:56,165 --> 00:02:59,130
ja tulevikus iterations--
läbimas massiivi again--

65
00:02:59,130 --> 00:03:01,280
me ei pea arvestama 6 enam.

66
00:03:01,280 --> 00:03:03,850
Meil on ainult kaaluda
sorteerimata elemendid

67
00:03:03,850 --> 00:03:06,299
Kui me vaatame kõrval paari.

68
00:03:06,299 --> 00:03:08,340
Nii oleme valmis ühe
läbida mull omamoodi.

69
00:03:08,340 --> 00:03:11,941
Nüüd me läheme tagasi küsimuse juurde,
korrata, kuni swap counter on 0.

70
00:03:11,941 --> 00:03:13,690
Noh swap counter
on 4, nii et me ei kavatse

71
00:03:13,690 --> 00:03:15,410
hoida korrates seda protsessi uuesti.

72
00:03:15,410 --> 00:03:19,180
>> Me läheme nullida swap counter
0, ja vaadata iga kõrvutistest.

73
00:03:19,180 --> 00:03:21,890
Nii hakkame koos 2 ja 1-- nad
rikkis, nii et me vahetada neid

74
00:03:21,890 --> 00:03:23,620
ja lisame 1 konverteerimist counter.

75
00:03:23,620 --> 00:03:25,490
2 ja 3, et nad on korras.

76
00:03:25,490 --> 00:03:27,060
Meil ei ole vaja midagi teha.

77
00:03:27,060 --> 00:03:28,420
3 ja 5 on korras.

78
00:03:28,420 --> 00:03:30,150
Meil ei ole vaja midagi teha seal.

79
00:03:30,150 --> 00:03:32,515
>> 5 ja 4, on nad läbi
tellimuse, ja nii me

80
00:03:32,515 --> 00:03:35,130
vaja vahetada neid ja lisada
1 konverteerimist counter.

81
00:03:35,130 --> 00:03:38,880
Ja nüüd me oleme liikunud 5,
suuruselt järgmine element,

82
00:03:38,880 --> 00:03:40,920
lõpuni sorteerimata portsjonina.

83
00:03:40,920 --> 00:03:44,360
Nii saame helistada, et
osa järjestatud osa.

84
00:03:44,360 --> 00:03:47,180
>> Nüüd sa vaadata
ekraan ja ilmselt võib öelda,

85
00:03:47,180 --> 00:03:50,130
kui ma saan, et massiivi
on järjestatud just nüüd.

86
00:03:50,130 --> 00:03:51,820
Aga me ei saa tõendada, et veel.

87
00:03:51,820 --> 00:03:54,359
Meil ei ole garantii
et see on järjestatud.

88
00:03:54,359 --> 00:03:56,900
Aga see on koht, kus swap
counter läheb mängu tulla.

89
00:03:56,900 --> 00:03:59,060
>> Nii et me oleme valmis läbima.

90
00:03:59,060 --> 00:04:00,357
Swap-counter on 2.

91
00:04:00,357 --> 00:04:02,190
Nii et me läheme kordama
Selle protsessi uuesti,

92
00:04:02,190 --> 00:04:04,290
korrata, kuni swap counter on 0.

93
00:04:04,290 --> 00:04:05,550
Taasta swap vastuollu 0.

94
00:04:05,550 --> 00:04:06,820
Nii me lähtestada.

95
00:04:06,820 --> 00:04:09,810
>> Nüüd vaatame iga kõrvutistest.

96
00:04:09,810 --> 00:04:11,880
See on selleks, 1 ja 2.

97
00:04:11,880 --> 00:04:13,590
2 ja 3 on selleks.

98
00:04:13,590 --> 00:04:15,010
3 ja 4 on selleks.

99
00:04:15,010 --> 00:04:19,250
Nii sel hetkel, märkate oleme valmis
vaadates iga kõrvutistest,

100
00:04:19,250 --> 00:04:22,530
kuid swap counter on ikka 0.

101
00:04:22,530 --> 00:04:25,520
>> Kui me ei ole minna
mis tahes elemente, siis nad

102
00:04:25,520 --> 00:04:28,340
peab olema selleks, mida
Tänu sellele protsessile.

103
00:04:28,340 --> 00:04:32,000
Ja nii kasutegur kehvasti,
et me arvuti teadlased armastan,

104
00:04:32,000 --> 00:04:35,560
on meil nüüd kuulutada
kogu massiiv tuleb

105
00:04:35,560 --> 00:04:38,160
sorteerida, sest me ei
on vahetada mistahes elemente.

106
00:04:38,160 --> 00:04:40,380
See on päris kena.

107
00:04:40,380 --> 00:04:43,260
>> Mis siis halvimal juhul
stsenaarium mull omamoodi?

108
00:04:43,260 --> 00:04:46,240
Halvimal juhul massiiv on
täiesti vastupidises järjekorras,

109
00:04:46,240 --> 00:04:49,870
ja nii me peame mull iga
Suure elemendid kõik

110
00:04:49,870 --> 00:04:51,780
Muide kogu massiivi.

111
00:04:51,780 --> 00:04:55,350
Ja me tegelikult ka on
mull kõik väikesed elemendid tagasi

112
00:04:55,350 --> 00:04:57,050
kõik teed kogu massiivi, liiga.

113
00:04:57,050 --> 00:05:01,950
Nii iga n elemendid on liikuda
kõigis teiste n elemente.

114
00:05:01,950 --> 00:05:04,102
Nii et halvimal juhul.

115
00:05:04,102 --> 00:05:05,810
Parimal juhul
stsenaariumi küll, see on

116
00:05:05,810 --> 00:05:07,880
veidi erinev valikut omamoodi.

117
00:05:07,880 --> 00:05:10,040
Massiiv on juba
järjestatud, kui me minema.

118
00:05:10,040 --> 00:05:12,550
Me ei pea tegema mingeid
vahetustehingute esimene pass.

119
00:05:12,550 --> 00:05:14,940
Nii et me oleks võinud vaadata
kell vähem elemente, eks?

120
00:05:14,940 --> 00:05:18,580
Me ei pea kordama seda
töödelda mitmeid kordi.

121
00:05:18,580 --> 00:05:19,540
>> Mida see tähendab?

122
00:05:19,540 --> 00:05:22,390
Mis siis halvimal juhul
mull sorteerida ning millised on

123
00:05:22,390 --> 00:05:25,330
Parimal juhul mull omamoodi?

124
00:05:25,330 --> 00:05:27,770
Kas sa vist seda?

125
00:05:27,770 --> 00:05:32,420
Halvimal juhul pead itereerima
kõigis n elemendid n korda.

126
00:05:32,420 --> 00:05:34,220
Nii et halvimal juhul on n ruudus.

127
00:05:34,220 --> 00:05:36,550
>> Kui massiiv on täiesti
sorteeritud aga sa ainult

128
00:05:36,550 --> 00:05:38,580
on vaadata iga
elementide üks kord.

129
00:05:38,580 --> 00:05:42,670
Ja kui swap counter on ikka 0,
sa ei saa öelda, see massiiv on järjestatud.

130
00:05:42,670 --> 00:05:45,780
Ja nii parimal juhul on see
tegelikult parem kui valikut

131
00:05:45,780 --> 00:05:49,230
sort-- see omega n.

132
00:05:49,230 --> 00:05:50,270
>> Ma olen Doug Lloyd.

133
00:05:50,270 --> 00:05:52,140
See on CS50.

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