>> MARK GROZEN-SMITH: Hi, jien Mark Grozen-Smith, u dan huwa Quicksort.
Eżatt bħal sort inserzjoni u bubble sort, Quicksort algoritmu għall-
issortjar lista jew firxa ta 'affarijiet.
Għas-sempliċità, ejja nassumu li dawk affarijiet huma biss interi, iżda
jafu li Quicksort taħdem għal aktar milli sempliċiment numri.
Quickstart huwa daqsxejn aktar ikkumplikata minn inserzjoni jew bużżieqa, imma hija
wkoll ferm aktar effiċjenti f'ħafna każijiet.
Stenna tieni.
Ma hu biss jgħidu "aktar każijiet, "mhux" kollha "?
Interessanti, l-ebda.
Mhux każijiet kollha huma l-istess.
Tinkwetax dwar dan id-dettall jekk inti ma bbenefikawx notazzjoni O big s'issa, iżda
Quicksort hija O (n kwadrat) algoritmu fl-agħar, bħal
inserzjoni jew sort bubble.
Madankollu, tipikament taġixxi ħafna aktar bħal m algoritmu Analog qodma.
Għaliex?
Aħna ser terġa 'lura għal dak aktar tard.
Iżda għal issa, ejja biss jitgħallmu kif Quicksort xogħlijiet.
>> Mela ejja jimxu permezz Quicksorting dan firxa ta 'numri interi minn iżgħar
għall-akbar.
Hawnhekk għandna l-interi 6, 5, 1, 3, 8, 4, 7, 9, u 2.
L-ewwel, aħna pick-element finali tal- dan array - f'dan il-każ, żewġ -
u sejħa li l-"pern." Sussegwentement, aħna tibda tħares lejn żewġ affarijiet -
wieħed, l-indiċi l-aktar baxx, li jiena ser nirreferi bħala joqogħdu għad-dritt ta '
il-ħajt, u, tnejn, il leftmost element, li jiena ser sejħa l-"attwali
element. "Dak li aħna qed tmur biex tagħmel hu tfittex l-elementi kollha l-oħra, oħrajn
mill-pern, u tpoġġi l-elementi kollha iżgħar mill-pern tal-
xellug tal-ħajt u dawk kollha akbar mill-pern tal-
dritt tal-ħajt.
Imbagħad, fl-aħħarnett, aħna ser qatra l-pern dritt fuq dik ħajt li titqiegħed bejn
il-numri iżgħar milli u l-numri akbar.
>> Mela ejja tagħmel dan.
Aqbad il-2, tpoġġi l-ħajt fil- bidu, u jitolbu l-6 l-"attwali
element. "Allura rridu nħarsu lejn element attwali tagħna, 6.
U peress li huwa akbar mill- 2, we ħalliha hemm għall-
dritt tal-ħajt.
Imbagħad, nimxu fuq li tħares lejn il-5 kif tagħna element attwali u tara li dan
huwa, għal darb'oħra, akbar mill-pern, hekk aħna tħalli fejn huwa fuq il-lemin
ġenb tal-ħajt.
Nimxu fuq.
Element attwali tagħna huwa issa 1, u - oh.
Dan huwa differenti issa.
L-element attwali issa huwa iżgħar minn il-pern, hekk irridu li tqiegħed lilha
għall-xellug tal-ħajt.
Biex tagħmel dan, ejja biss jaqilbu l- element attwali bl-indiċi l-aktar baxx
seduta biss għad-dritt tal-ħajt.
Issa, nimxu il-ħajt up indiċi wieħed sabiex l-1 hija fuq ix-xellug
ġenb tal-ħajt issa.
>> Stenna.
I biss mħallta l-elementi fuq il- lemin tal-ħajt, ma I?
Tinkwetax.
Li l-multa.
L-unika ħaġa li aħna kura dwar għal issa hija li dawn l-elementi kollha għall-
dritt tal-ħajt huma akbar mill-pern.
Ebda ordni attwali huwa preżunt s'issa.
>> Issa, lura għall-issortjar.
Allura aħna tkompli fuq tħares lejn il-bqija tal-elementi.
U f'dan il-każ, naraw li hemm ebda elementi ta 'inqas mill-
pern, hekk aħna jħallu lilhom kollha fuq il-lemin tal-ħajt.
Fl-aħħarnett, irridu jiksbu l-element attwali u tara li hija l-pern.
Issa, dan ifisser li għandna żewġ sezzjonijiet tal-firxa, l-ewwel wieħed
żgħir fuq il-pern u fuq ix-xellug tal-ħajt, u t-tieni benesseri
akbar mill-pern tal- lemin tal-ħajt.
Aħna tixtieq li tqiegħed l-element tal-pern bejn it-tnejn, u allura aħna ser tkun taf
li l-pern tiegħu huwa fl-dritt tagħha post Issortjati finali.
Allura aħna jaqilbu l-ewwel element fuq l- lemin tal-ħajt bil-pern,
u nafu l-pern tal- fil-pożizzjoni dritt tagħha.
>> Aħna mbagħad irrepeti dan il-proċess għall- subarrays xellug u tal-lemin tal-pern.
Mill-aħħar subarray hija biss waħda element twil, nafu li l-diġà
Issortjati għaliex kif tista 'tkun' il barra ta ' tordna jekk int element wieħed biss?
Għall-lemin tal-subarray, aħna tara li l-pern huwa 5, u l-ħajt
huwa biss ix-xellug tal-6.
U l-element attwali wkoll tibda bħala l-6.
Allura 6 huwa ikbar minn 5.
Aħna tħalli fejn huwa fuq il- lemin tal-ħajt.
Ngħaddu issa għal, 3 huwa inqas minn 5.
Allura aħna jaqilbu l-ewwel element biss id-dritt tal-ħajt.
Issa, I għamel il-ħajt up wieħed.
Issa, jimxu fuq il-8.
8 huwa ikbar minn 5, u hekk aħna jitilqu minnu.
Il 4 hija anqas minn 5, hekk aħna jaqilbu.
U fuq.
>> Kull darba li aħna irrepeti l-proċess fuq l- naħat tax-xellug u tal-lemin ta 'l-array. aħna
jagħżlu pern u jagħmlu l-paraguni u joħolqu livell ieħor ta 'xellug u
subarrays dritt.
Din is-sejħa jirrikorri se tkompli sa aħna jilħqu t-tmiem meta konna
maqsuma l-firxa globali fis biss subarrays ta 'tul 1.
Minn hemm, nafu l-array huwa magħżul għaliex kull element għandu, fi
F'xi punt, kien pern.
Fi kliem ieħor, għal kull element, kollha -numri fuq ix-xellug huma inqas
valuri u l-numri fil- dritt għandhom valuri akbar.
>> Dan il-metodu jaħdem tajjeb ħafna jekk l- valur tal-pern magħżul huwa
madwar fin-nofs firxa tal-valuri lista.
Dan ikun ifisser li, wara nimxu elementi madwar, hemm madwar bħala ħafna
elementi għall-xellug tal-pern kif hemm lejn il-lemin.
U n-natura-firda u conquer tal- Algoritmu Quicksort mbagħad tittieħed
vantaġġ sħiħ.
Dan joħloq runtime ta 'O (n log n,) n għaliex għandna nagħmlu n minus 1
paraguni fuq kull ġenerazzjoni u log n għaliex għandna li jaqsam il-lista
log n darbiet.
Madankollu, fl-agħar każijiet, dan algoritmu jista 'attwalment jiġi O (n
kwadrat.) Ejja ngħidu fuq kull ġenerazzjoni, l-pern biss hekk jiġri li jkun l-
iżgħar jew akbar ta 'l- numri aħna qed issortjar.
Dan ikun ifisser jitkissru l-lista n ħinijiet u teħid n minus 1
paraguni kull wieħed ħin.
Għalhekk, o tas n kwadru.
>> Kif nistgħu jtejbu l-metodu?
Mod wieħed tajjeb biex itejbu l-metodu huwa biex inaqqsu l-probabbiltà li
l-runtime huwa fil-fatt qatt o tar n kwadru.
Ftakar dan agħar, agħar każ jista 'jiġri biss meta l-
pern magħżul huwa dejjem l-ogħla jew il-valur aktar baxx fil-firxa.
Biex tiżgura li dan huwa inqas probabbli li jiġri, nistgħu nsibu l-pern minn
jagħżlu elementi multipli u tieħu l-valur medjan.
>> Jisimni Mark Grozen-Smith, u dan huwa CS50.
>> Għas-sempliċità, ejja nassumu li dawk affarijiet huma biss interi, iżda
taf li Quicksert -
Quicksert?
Jiddispjacini.
>> Hawnhekk għandna l-interi 6, 5, 1, 3, 8, 4, 9.
>> SPEAKER 1: Really?
>> SPEAKER 2: M'għandekx tieqaf hemm.
>> SPEAKER 1: Really?