1
00:00:00,000 --> 00:00:07,270

2
00:00:07,270 --> 00:00:10,390
>> MARK GROZEN-SMITH: Hej, jeg er Mark
Grozen-Smith, og det er QuickSort.

3
00:00:10,390 --> 00:00:13,520
Ligesom indsættelse sortere og boble
sortere QuickSort er en algoritme til

4
00:00:13,520 --> 00:00:15,720
sortering en liste eller en matrix af ting.

5
00:00:15,720 --> 00:00:19,080
For nemheds skyld lad os antage, at de
ting er bare heltal, men

6
00:00:19,080 --> 00:00:22,060
vide, at QuickSort arbejder for
mere end blot tal.

7
00:00:22,060 --> 00:00:24,720
Quickstart er en smule mere kompliceret
end indsættelse eller boble, men det er

8
00:00:24,720 --> 00:00:27,560
også langt mere effektiv
i de fleste tilfælde.

9
00:00:27,560 --> 00:00:28,150
Vent et sekund.

10
00:00:28,150 --> 00:00:30,760
Sagde han "mest
tilfælde ", ikke" alle "?

11
00:00:30,760 --> 00:00:31,710
Interessant, no.

12
00:00:31,710 --> 00:00:33,560
Ikke alle tilfælde er de samme.

13
00:00:33,560 --> 00:00:36,650
Må ikke bekymre dig om denne detalje, hvis du
har ikke set store O notation endnu, men

14
00:00:36,650 --> 00:00:39,730
QuickSort er en O (n kvadreret) algoritme
i værste fald, ligesom

15
00:00:39,730 --> 00:00:41,430
indsættelse eller boble slags.

16
00:00:41,430 --> 00:00:44,950
Men det fungerer typisk meget mere
som en gammel analog m algoritme.

17
00:00:44,950 --> 00:00:45,750
Hvorfor?

18
00:00:45,750 --> 00:00:46,810
Det vender vi tilbage til senere.

19
00:00:46,810 --> 00:00:49,610
Men for nu, lad os bare lære
hvordan QuickSort fungerer.

20
00:00:49,610 --> 00:00:53,080
>> Så lad os gå gennem Quicksorting dette
vifte af heltal fra den mindste

21
00:00:53,080 --> 00:00:54,260
til den største.

22
00:00:54,260 --> 00:01:00,110
Her har vi de hele tal 6,
5, 1, 3, 8, 4, 7, 9 og 2.

23
00:01:00,110 --> 00:01:03,480
Først, vi vælger det sidste element af
dette array - i dette tilfælde to -

24
00:01:03,480 --> 00:01:06,870
og kalder det en "pivot". Desuden, vi
begynder at se på to ting -

25
00:01:06,870 --> 00:01:10,220
ene, det laveste indeks, som jeg vil henvise
som opholder sig til højre for

26
00:01:10,220 --> 00:01:13,970
væggen, og, to, længst til venstre
element, som jeg vil kalde "den nuværende

27
00:01:13,970 --> 00:01:17,260
element. "Hvad vi kommer til at gøre, er
se alle de andre elementer, andre

28
00:01:17,260 --> 00:01:20,930
end pivot, og lægge alle de elementer
mindre end drejetappen til

29
00:01:20,930 --> 00:01:24,140
venstre væg og alle de
større end pivot til

30
00:01:24,140 --> 00:01:25,570
højre for væggen.

31
00:01:25,570 --> 00:01:29,560
Så endelig, vil vi droppe pivot
lige på den mur at sætte det mellem

32
00:01:29,560 --> 00:01:32,970
alle tal er mindre end den
og alle tal større.

33
00:01:32,970 --> 00:01:34,460
>> Så lad os gøre det.

34
00:01:34,460 --> 00:01:38,540
Saml de 2, sætte væggen i
begyndelse, og kalder 6 "den nuværende

35
00:01:38,540 --> 00:01:41,590
element. "Så vi ønsker at se på
vores aktuelle element, 6.

36
00:01:41,590 --> 00:01:44,200
Og da det er større end
2, vi overlade det der til

37
00:01:44,200 --> 00:01:45,610
højre for væggen.

38
00:01:45,610 --> 00:01:48,980
Derefter bevæger vi os videre til at se på de 5 som vores
aktuelle element og se, at denne

39
00:01:48,980 --> 00:01:51,840
er igen større end drejetappen, så vi
forlade det, hvor det er på den højre

40
00:01:51,840 --> 00:01:53,190
side af væggen.

41
00:01:53,190 --> 00:01:53,880
Vi videre.

42
00:01:53,880 --> 00:01:56,750
Vores nuværende element er
nu 1, og - oh.

43
00:01:56,750 --> 00:01:58,030
Det er anderledes nu.

44
00:01:58,030 --> 00:02:00,890
Den aktuelle element er nu mindre end
pivot, så vi ønsker at sætte det

45
00:02:00,890 --> 00:02:02,570
til venstre for væggen.

46
00:02:02,570 --> 00:02:06,555
For at gøre dette, lad os bare skifte
aktuelle element med det laveste indeks

47
00:02:06,555 --> 00:02:07,970
sidder lige til højre for væggen.

48
00:02:07,970 --> 00:02:14,050

49
00:02:14,050 --> 00:02:17,570
Nu bevæger vi muren op ene indeks
så 1 er til venstre

50
00:02:17,570 --> 00:02:19,750
side af væggen nu.

51
00:02:19,750 --> 00:02:20,310
>> Vent.

52
00:02:20,310 --> 00:02:23,450
Jeg bare blandet op elementerne på
højre side af væggen, gjorde jeg ikke?

53
00:02:23,450 --> 00:02:23,890
Må ikke bekymre dig.

54
00:02:23,890 --> 00:02:24,930
Det er fint.

55
00:02:24,930 --> 00:02:27,570
Det eneste, vi bekymrer os om for nu
er, at alle disse elementer til

56
00:02:27,570 --> 00:02:29,570
højre for væggen er større
end pivot.

57
00:02:29,570 --> 00:02:31,760
Forudsættes ingen faktiske orden endnu.

58
00:02:31,760 --> 00:02:33,200
>> Nu tilbage til sortering.

59
00:02:33,200 --> 00:02:35,840
Så vi fortsætter med at se på
resten af ​​elementerne.

60
00:02:35,840 --> 00:02:39,075
Og i dette tilfælde ser vi, at der er
ingen andre elementer mindre end

61
00:02:39,075 --> 00:02:42,100
pivot, så vi forlader dem alle på
højre side af væggen.

62
00:02:42,100 --> 00:02:45,980
Endelig får vi at det aktuelle element
og se, at det er omdrejningspunktet.

63
00:02:45,980 --> 00:02:48,830
Nu betyder det, at vi har to
sektioner af matrixen, den første er

64
00:02:48,830 --> 00:02:51,820
små på pivot og på venstre side
af væggen, og den anden er

65
00:02:51,820 --> 00:02:54,500
større end pivot til
højre side af væggen.

66
00:02:54,500 --> 00:02:57,040
Vi ønsker at sætte pivot element mellem
de to, og så vil vi vide

67
00:02:57,040 --> 00:03:01,000
at pivot er i sin ret
endelig sorterede sted.

68
00:03:01,000 --> 00:03:04,980
Så vi tænder det første element på
højre side af væggen med pivot,

69
00:03:04,980 --> 00:03:06,410
og vi kender pivot s
i sin rigtige position.

70
00:03:06,410 --> 00:03:11,130

71
00:03:11,130 --> 00:03:15,650
>> Vi derefter gentage denne proces for den
subarrays venstre og højre for pivot.

72
00:03:15,650 --> 00:03:18,700
Siden sidste subarray er kun én
element lang, vi ved, det er allerede

73
00:03:18,700 --> 00:03:22,480
sorteret fordi hvordan kan du være ude af
ordre, hvis du er kun et element?

74
00:03:22,480 --> 00:03:28,860
På højre side af undergrupperingen vi
se, at pivot er 5, og væggen

75
00:03:28,860 --> 00:03:32,250
er lige til venstre for 6.

76
00:03:32,250 --> 00:03:34,970
Og den nuværende element også
starter ud som 6.

77
00:03:34,970 --> 00:03:36,200
Så 6 er større end 5.

78
00:03:36,200 --> 00:03:38,590
Vi overlader det, hvor det er på den
højre side af væggen.

79
00:03:38,590 --> 00:03:41,060
Nu bevæger sig på, 3 er mindre end 5..

80
00:03:41,060 --> 00:03:44,160
Så vi skifter det med det første element
lige til højre for væggen.

81
00:03:44,160 --> 00:03:47,944

82
00:03:47,944 --> 00:03:50,750
Nu flyttede jeg muren op én.

83
00:03:50,750 --> 00:03:53,010
Nu går videre til 8..

84
00:03:53,010 --> 00:03:56,480
8 er større end 5,
og så vi forlader den.

85
00:03:56,480 --> 00:03:58,720
De 4 er mindre end 5, så vi skifte det.

86
00:03:58,720 --> 00:04:02,950

87
00:04:02,950 --> 00:04:03,570
Og på.

88
00:04:03,570 --> 00:04:04,820
Og på.

89
00:04:04,820 --> 00:04:10,190

90
00:04:10,190 --> 00:04:13,670
>> Hver gang vi gentage processen på
venstre og højre side af array. vi

91
00:04:13,670 --> 00:04:17,010
vælge en pivot og gøre sammenligningerne
og skabe et andet niveau af venstre og

92
00:04:17,010 --> 00:04:18,240
rigtige subarrays.

93
00:04:18,240 --> 00:04:21,500
Denne rekursivt kald vil fortsætte indtil
vi når til slutningen, når vi har

94
00:04:21,500 --> 00:04:25,290
opdeles den samlede array i
bare subarrays af længde 1.

95
00:04:25,290 --> 00:04:28,060
Derfra ved vi array sorteres
fordi hvert element har på

96
00:04:28,060 --> 00:04:29,330
et tidspunkt været en drejetap.

97
00:04:29,330 --> 00:04:32,720
Med andre ord, for hvert element, alle
tallene til venstre er mindre

98
00:04:32,720 --> 00:04:36,420
værdier og alle de numre til
højre har større værdier.

99
00:04:36,420 --> 00:04:38,980
>> Denne fremgangsmåde fungerer godt, hvis
værdien af ​​den valgte pivot er

100
00:04:38,980 --> 00:04:41,930
omtrent i midten
vifte af listeværdierne.

101
00:04:41,930 --> 00:04:45,630
Dette ville betyde, at efter vi flytter
elementer rundt, er der omtrent lige så mange

102
00:04:45,630 --> 00:04:48,390
elementer til venstre for pivot
, som der er til højre.

103
00:04:48,390 --> 00:04:52,380
Og del-og-hersk karakter
QuickSort algoritme tages derefter

104
00:04:52,380 --> 00:04:53,850
fuld fordel af.

105
00:04:53,850 --> 00:04:57,500
Dette skaber en runtime af O (n log n,)
n, fordi vi har at gøre n minus 1

106
00:04:57,500 --> 00:05:01,640
sammenligninger af hver generation og log
n fordi vi er nødt til at opdele listen

107
00:05:01,640 --> 00:05:03,210
log n gange.

108
00:05:03,210 --> 00:05:06,160
Men i de værste tilfælde, dette
algoritme kan faktisk være O (n

109
00:05:06,160 --> 00:05:09,850
potens.) Antag på hver generation,
omdrejningspunktet bare så sker for at være den

110
00:05:09,850 --> 00:05:12,520
mindste eller den største af de
numre vi sortering.

111
00:05:12,520 --> 00:05:15,870
Dette ville betyde at bryde ned på listen
n gange og Tage N minus 1

112
00:05:15,870 --> 00:05:17,690
sammenligninger hver eneste gang.

113
00:05:17,690 --> 00:05:20,490
Således o n potens.

114
00:05:20,490 --> 00:05:22,000
>> Hvordan kan vi forbedre den metode?

115
00:05:22,000 --> 00:05:25,100
En god måde at forbedre metoden er
at skære ned på sandsynligheden for, at

116
00:05:25,100 --> 00:05:28,150
runtime er nogensinde rent faktisk
o n potens.

117
00:05:28,150 --> 00:05:31,860
Husk dette værste worst case scenario
kan kun ske, når

118
00:05:31,860 --> 00:05:35,320
pivot valgt er altid den højeste
eller laveste værdi i array.

119
00:05:35,320 --> 00:05:38,630
For at sikre dette er mindre tilbøjelige til at ske,
vi kan finde pivot

120
00:05:38,630 --> 00:05:42,610
vælge flere elementer og
tager medianen.

121
00:05:42,610 --> 00:05:44,650
>> Mit navn er Mark Grozen-Smith,
og dette er CS50.

122
00:05:44,650 --> 00:05:47,790

123
00:05:47,790 --> 00:05:50,930
>> For nemheds skyld lad os antage, at de
ting er bare heltal, men

124
00:05:50,930 --> 00:05:51,970
ved, at Quicksert -

125
00:05:51,970 --> 00:05:53,160
Quicksert?

126
00:05:53,160 --> 00:05:55,200
Undskyld.

127
00:05:55,200 --> 00:06:02,000
>> Her har vi de hele tal
6, 5, 1, 3, 8, 4, 9.

128
00:06:02,000 --> 00:06:03,200
>> SPEAKER 1: Virkelig?

129
00:06:03,200 --> 00:06:04,850
>> SPEAKER 2: Du må ikke stoppe der.

130
00:06:04,850 --> 00:06:06,100
>> SPEAKER 1: Virkelig?

131
00:06:06,100 --> 00:06:08,491