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

2
00:00:07,270 --> 00:00:10,390
>> MARK GROZEN-SMITH: Hi, jien Mark
Grozen-Smith, u dan huwa Quicksort.

3
00:00:10,390 --> 00:00:13,520
Eżatt bħal sort inserzjoni u bubble
sort, Quicksort algoritmu għall-

4
00:00:13,520 --> 00:00:15,720
issortjar lista jew firxa ta 'affarijiet.

5
00:00:15,720 --> 00:00:19,080
Għas-sempliċità, ejja nassumu li dawk
affarijiet huma biss interi, iżda

6
00:00:19,080 --> 00:00:22,060
jafu li Quicksort taħdem għal
aktar milli sempliċiment numri.

7
00:00:22,060 --> 00:00:24,720
Quickstart huwa daqsxejn aktar ikkumplikata
minn inserzjoni jew bużżieqa, imma hija

8
00:00:24,720 --> 00:00:27,560
wkoll ferm aktar effiċjenti
f'ħafna każijiet.

9
00:00:27,560 --> 00:00:28,150
Stenna tieni.

10
00:00:28,150 --> 00:00:30,760
Ma hu biss jgħidu "aktar
każijiet, "mhux" kollha "?

11
00:00:30,760 --> 00:00:31,710
Interessanti, l-ebda.

12
00:00:31,710 --> 00:00:33,560
Mhux każijiet kollha huma l-istess.

13
00:00:33,560 --> 00:00:36,650
Tinkwetax dwar dan id-dettall jekk inti
ma bbenefikawx notazzjoni O big s'issa, iżda

14
00:00:36,650 --> 00:00:39,730
Quicksort hija O (n kwadrat) algoritmu
fl-agħar, bħal

15
00:00:39,730 --> 00:00:41,430
inserzjoni jew sort bubble.

16
00:00:41,430 --> 00:00:44,950
Madankollu, tipikament taġixxi ħafna aktar
bħal m algoritmu Analog qodma.

17
00:00:44,950 --> 00:00:45,750
Għaliex?

18
00:00:45,750 --> 00:00:46,810
Aħna ser terġa 'lura għal dak aktar tard.

19
00:00:46,810 --> 00:00:49,610
Iżda għal issa, ejja biss jitgħallmu
kif Quicksort xogħlijiet.

20
00:00:49,610 --> 00:00:53,080
>> Mela ejja jimxu permezz Quicksorting dan
firxa ta 'numri interi minn iżgħar

21
00:00:53,080 --> 00:00:54,260
għall-akbar.

22
00:00:54,260 --> 00:01:00,110
Hawnhekk għandna l-interi 6,
5, 1, 3, 8, 4, 7, 9, u 2.

23
00:01:00,110 --> 00:01:03,480
L-ewwel, aħna pick-element finali tal-
dan array - f'dan il-każ, żewġ -

24
00:01:03,480 --> 00:01:06,870
u sejħa li l-"pern." Sussegwentement, aħna
tibda tħares lejn żewġ affarijiet -

25
00:01:06,870 --> 00:01:10,220
wieħed, l-indiċi l-aktar baxx, li jiena ser nirreferi
bħala joqogħdu għad-dritt ta '

26
00:01:10,220 --> 00:01:13,970
il-ħajt, u, tnejn, il leftmost
element, li jiena ser sejħa l-"attwali

27
00:01:13,970 --> 00:01:17,260
element. "Dak li aħna qed tmur biex tagħmel hu
tfittex l-elementi kollha l-oħra, oħrajn

28
00:01:17,260 --> 00:01:20,930
mill-pern, u tpoġġi l-elementi kollha
iżgħar mill-pern tal-

29
00:01:20,930 --> 00:01:24,140
xellug tal-ħajt u dawk kollha
akbar mill-pern tal-

30
00:01:24,140 --> 00:01:25,570
dritt tal-ħajt.

31
00:01:25,570 --> 00:01:29,560
Imbagħad, fl-aħħarnett, aħna ser qatra l-pern
dritt fuq dik ħajt li titqiegħed bejn

32
00:01:29,560 --> 00:01:32,970
il-numri iżgħar milli
u l-numri akbar.

33
00:01:32,970 --> 00:01:34,460
>> Mela ejja tagħmel dan.

34
00:01:34,460 --> 00:01:38,540
Aqbad il-2, tpoġġi l-ħajt fil-
bidu, u jitolbu l-6 l-"attwali

35
00:01:38,540 --> 00:01:41,590
element. "Allura rridu nħarsu lejn
element attwali tagħna, 6.

36
00:01:41,590 --> 00:01:44,200
U peress li huwa akbar mill-
2, we ħalliha hemm għall-

37
00:01:44,200 --> 00:01:45,610
dritt tal-ħajt.

38
00:01:45,610 --> 00:01:48,980
Imbagħad, nimxu fuq li tħares lejn il-5 kif tagħna
element attwali u tara li dan

39
00:01:48,980 --> 00:01:51,840
huwa, għal darb'oħra, akbar mill-pern, hekk aħna
tħalli fejn huwa fuq il-lemin

40
00:01:51,840 --> 00:01:53,190
ġenb tal-ħajt.

41
00:01:53,190 --> 00:01:53,880
Nimxu fuq.

42
00:01:53,880 --> 00:01:56,750
Element attwali tagħna huwa
issa 1, u - oh.

43
00:01:56,750 --> 00:01:58,030
Dan huwa differenti issa.

44
00:01:58,030 --> 00:02:00,890
L-element attwali issa huwa iżgħar minn
il-pern, hekk irridu li tqiegħed lilha

45
00:02:00,890 --> 00:02:02,570
għall-xellug tal-ħajt.

46
00:02:02,570 --> 00:02:06,555
Biex tagħmel dan, ejja biss jaqilbu l-
element attwali bl-indiċi l-aktar baxx

47
00:02:06,555 --> 00:02:07,970
seduta biss għad-dritt tal-ħajt.

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

49
00:02:14,050 --> 00:02:17,570
Issa, nimxu il-ħajt up indiċi wieħed
sabiex l-1 hija fuq ix-xellug

50
00:02:17,570 --> 00:02:19,750
ġenb tal-ħajt issa.

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

52
00:02:20,310 --> 00:02:23,450
I biss mħallta l-elementi fuq il-
lemin tal-ħajt, ma I?

53
00:02:23,450 --> 00:02:23,890
Tinkwetax.

54
00:02:23,890 --> 00:02:24,930
Li l-multa.

55
00:02:24,930 --> 00:02:27,570
L-unika ħaġa li aħna kura dwar għal issa
hija li dawn l-elementi kollha għall-

56
00:02:27,570 --> 00:02:29,570
dritt tal-ħajt huma akbar
mill-pern.

57
00:02:29,570 --> 00:02:31,760
Ebda ordni attwali huwa preżunt s'issa.

58
00:02:31,760 --> 00:02:33,200
>> Issa, lura għall-issortjar.

59
00:02:33,200 --> 00:02:35,840
Allura aħna tkompli fuq tħares lejn
il-bqija tal-elementi.

60
00:02:35,840 --> 00:02:39,075
U f'dan il-każ, naraw li hemm
ebda elementi ta 'inqas mill-

61
00:02:39,075 --> 00:02:42,100
pern, hekk aħna jħallu lilhom kollha fuq
il-lemin tal-ħajt.

62
00:02:42,100 --> 00:02:45,980
Fl-aħħarnett, irridu jiksbu l-element attwali
u tara li hija l-pern.

63
00:02:45,980 --> 00:02:48,830
Issa, dan ifisser li għandna żewġ
sezzjonijiet tal-firxa, l-ewwel wieħed

64
00:02:48,830 --> 00:02:51,820
żgħir fuq il-pern u fuq ix-xellug
tal-ħajt, u t-tieni benesseri

65
00:02:51,820 --> 00:02:54,500
akbar mill-pern tal-
lemin tal-ħajt.

66
00:02:54,500 --> 00:02:57,040
Aħna tixtieq li tqiegħed l-element tal-pern bejn
it-tnejn, u allura aħna ser tkun taf

67
00:02:57,040 --> 00:03:01,000
li l-pern tiegħu huwa fl-dritt tagħha
post Issortjati finali.

68
00:03:01,000 --> 00:03:04,980
Allura aħna jaqilbu l-ewwel element fuq l-
lemin tal-ħajt bil-pern,

69
00:03:04,980 --> 00:03:06,410
u nafu l-pern tal-
fil-pożizzjoni dritt tagħha.

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

71
00:03:11,130 --> 00:03:15,650
>> Aħna mbagħad irrepeti dan il-proċess għall-
subarrays xellug u tal-lemin tal-pern.

72
00:03:15,650 --> 00:03:18,700
Mill-aħħar subarray hija biss waħda
element twil, nafu li l-diġà

73
00:03:18,700 --> 00:03:22,480
Issortjati għaliex kif tista 'tkun' il barra ta '
tordna jekk int element wieħed biss?

74
00:03:22,480 --> 00:03:28,860
Għall-lemin tal-subarray, aħna
tara li l-pern huwa 5, u l-ħajt

75
00:03:28,860 --> 00:03:32,250
huwa biss ix-xellug tal-6.

76
00:03:32,250 --> 00:03:34,970
U l-element attwali wkoll
tibda bħala l-6.

77
00:03:34,970 --> 00:03:36,200
Allura 6 huwa ikbar minn 5.

78
00:03:36,200 --> 00:03:38,590
Aħna tħalli fejn huwa fuq il-
lemin tal-ħajt.

79
00:03:38,590 --> 00:03:41,060
Ngħaddu issa għal, 3 huwa inqas minn 5.

80
00:03:41,060 --> 00:03:44,160
Allura aħna jaqilbu l-ewwel element
biss id-dritt tal-ħajt.

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

82
00:03:47,944 --> 00:03:50,750
Issa, I għamel il-ħajt up wieħed.

83
00:03:50,750 --> 00:03:53,010
Issa, jimxu fuq il-8.

84
00:03:53,010 --> 00:03:56,480
8 huwa ikbar minn 5,
u hekk aħna jitilqu minnu.

85
00:03:56,480 --> 00:03:58,720
Il 4 hija anqas minn 5, hekk aħna jaqilbu.

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

87
00:04:02,950 --> 00:04:03,570
U fuq.

88
00:04:03,570 --> 00:04:04,820
U fuq.

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

90
00:04:10,190 --> 00:04:13,670
>> Kull darba li aħna irrepeti l-proċess fuq l-
naħat tax-xellug u tal-lemin ta 'l-array. aħna

91
00:04:13,670 --> 00:04:17,010
jagħżlu pern u jagħmlu l-paraguni
u joħolqu livell ieħor ta 'xellug u

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

93
00:04:18,240 --> 00:04:21,500
Din is-sejħa jirrikorri se tkompli sa
aħna jilħqu t-tmiem meta konna

94
00:04:21,500 --> 00:04:25,290
maqsuma l-firxa globali fis
biss subarrays ta 'tul 1.

95
00:04:25,290 --> 00:04:28,060
Minn hemm, nafu l-array huwa magħżul
għaliex kull element għandu, fi

96
00:04:28,060 --> 00:04:29,330
F'xi punt, kien pern.

97
00:04:29,330 --> 00:04:32,720
Fi kliem ieħor, għal kull element, kollha
-numri fuq ix-xellug huma inqas

98
00:04:32,720 --> 00:04:36,420
valuri u l-numri fil-
dritt għandhom valuri akbar.

99
00:04:36,420 --> 00:04:38,980
>> Dan il-metodu jaħdem tajjeb ħafna jekk l-
valur tal-pern magħżul huwa

100
00:04:38,980 --> 00:04:41,930
madwar fin-nofs
firxa tal-valuri lista.

101
00:04:41,930 --> 00:04:45,630
Dan ikun ifisser li, wara nimxu
elementi madwar, hemm madwar bħala ħafna

102
00:04:45,630 --> 00:04:48,390
elementi għall-xellug tal-pern
kif hemm lejn il-lemin.

103
00:04:48,390 --> 00:04:52,380
U n-natura-firda u conquer tal-
Algoritmu Quicksort mbagħad tittieħed

104
00:04:52,380 --> 00:04:53,850
vantaġġ sħiħ.

105
00:04:53,850 --> 00:04:57,500
Dan joħloq runtime ta 'O (n log n,)
n għaliex għandna nagħmlu n minus 1

106
00:04:57,500 --> 00:05:01,640
paraguni fuq kull ġenerazzjoni u log
n għaliex għandna li jaqsam il-lista

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

108
00:05:03,210 --> 00:05:06,160
Madankollu, fl-agħar każijiet, dan
algoritmu jista 'attwalment jiġi O (n

109
00:05:06,160 --> 00:05:09,850
kwadrat.) Ejja ngħidu fuq kull ġenerazzjoni,
l-pern biss hekk jiġri li jkun l-

110
00:05:09,850 --> 00:05:12,520
iżgħar jew akbar ta 'l-
numri aħna qed issortjar.

111
00:05:12,520 --> 00:05:15,870
Dan ikun ifisser jitkissru l-lista
n ħinijiet u teħid n minus 1

112
00:05:15,870 --> 00:05:17,690
paraguni kull wieħed ħin.

113
00:05:17,690 --> 00:05:20,490
Għalhekk, o tas n kwadru.

114
00:05:20,490 --> 00:05:22,000
>> Kif nistgħu jtejbu l-metodu?

115
00:05:22,000 --> 00:05:25,100
Mod wieħed tajjeb biex itejbu l-metodu huwa
biex inaqqsu l-probabbiltà li

116
00:05:25,100 --> 00:05:28,150
l-runtime huwa fil-fatt qatt
o tar n kwadru.

117
00:05:28,150 --> 00:05:31,860
Ftakar dan agħar, agħar każ
jista 'jiġri biss meta l-

118
00:05:31,860 --> 00:05:35,320
pern magħżul huwa dejjem l-ogħla
jew il-valur aktar baxx fil-firxa.

119
00:05:35,320 --> 00:05:38,630
Biex tiżgura li dan huwa inqas probabbli li jiġri,
nistgħu nsibu l-pern minn

120
00:05:38,630 --> 00:05:42,610
jagħżlu elementi multipli u
tieħu l-valur medjan.

121
00:05:42,610 --> 00:05:44,650
>> Jisimni Mark Grozen-Smith,
u dan huwa CS50.

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

123
00:05:47,790 --> 00:05:50,930
>> Għas-sempliċità, ejja nassumu li dawk
affarijiet huma biss interi, iżda

124
00:05:50,930 --> 00:05:51,970
taf li Quicksert -

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

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

127
00:05:55,200 --> 00:06:02,000
>> Hawnhekk għandna l-interi
6, 5, 1, 3, 8, 4, 9.

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

129
00:06:03,200 --> 00:06:04,850
>> SPEAKER 2: M'għandekx tieqaf hemm.

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

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