>> MARK GROZEN-Smith: Hi, Unë jam Mark Grozen-Smith, dhe kjo është Quicksort.
Ashtu si lloj e hyrjes dhe flluskë lloj, Quicksort është një algoritmi për
sorting një listë ose një grup të gjëra.
Për thjeshtësi, le të supozojmë se ata gjërat janë vetëm numra të plotë, por
e di se Quicksort punon për më shumë se vetëm numra.
QuickStart është pak më e komplikuar se futje ose flluskë, por është e
edhe shumë më të efektshme në shumicën e rasteve.
Prisni një të dytë.
Deshi të thotë ai "më të raste, "jo" të gjitha "?
Interesante, nr.
Jo të gjitha rastet janë të njëjta.
Mos u shqetësoni për këtë hollësi nëse ju nuk e kanë parë o simbol të madh, por
Quicksort është O (n katror) algorithm në më të keq, ashtu si
futje ose flluskë lloj.
Megjithatë, ai zakonisht vepron shumë më tepër si një analog m algoritmi të vjetër.
Pse?
Ne do të kthehen në atë më vonë.
Por tani për tani, le të vetëm të mësojnë se si funksionon Quicksort.
>> Pra, le të ecin nëpër këtë Quicksorting grup i integers nga më të vogël
të më e madhe.
Këtu kemi integers 6, 5, 1, 3, 8, 4, 7, 9, dhe 2.
Së pari, ne kemi marr elementin final të kjo array - në këtë rast, dy -
dhe thirrje që të "strumbullar." Tjetra, ne fillojnë të shikojnë në dy gjëra -
një, indeksi të ulët, të cilën unë do të referohen si për të qëndruar në të djathtë të
mur, dhe, dy të, i pari nga e majta element, që unë do të thërrasë "e tanishme
element. "Ajo që ne jemi duke shkuar për të bërë është shikoni të gjitha elementet e tjera, të tjera
se bosht, dhe të vënë të gjitha elementet vogël se boshti sa më
majtë të murit dhe të gjithë ata mëdha se boshti te
drejtën e murit.
Pastaj, më në fund, ne do të heqin të strumbullar të drejtë në atë mur ta vënë atë në mes të
të gjitha numrat më të vogla se sa ajo dhe të gjitha numrat më të mëdha.
>> Pra, le ta bëjmë atë.
Marr 2, vënë në mur duke filluar, dhe thirrjen e 6 e "aktuale
element. "Pra, ne duam të shohim në Elementi ynë aktual, 6.
Dhe që kjo është më e madhe se 2, ne të lënë aty për të
drejtën e murit.
Pastaj, ne shkojmë për të parë në 5 tonë si element i tanishëm dhe të shohim se ky
është, perseri, e madhe se boshti, kështu ne lënë atë aty ku është në të djathtë
anë e murit.
Ne lëvizë.
Element jonë e tanishme është tani 1, dhe - oh.
Kjo është e ndryshme tani.
Elementi i tanishëm tani është më i vogël se strumbullar, kështu që ne duam të vënë atë
majtas te murit.
Për ta bërë këtë, le të vetëm kaloni element i tanishëm me indeksin më të ulët
ulur vetëm në të djathtë të murit.
Tani, ne shkojmë muret lart një indeks ashtu 1 është majtas
anë e murit tani.
>> Prisni.
Unë vetëm të përziera elementet në anën e djathtë të murit, apo jo?
Mos u shqetësoni.
Kjo është në rregull.
E vetmja gjë ne lidhje me kujdes për tani është se të gjitha këto elemente të
drejta e murit janë më të mëdha se boshti.
Nuk ka mënyrë aktuale supozohet ende.
>> Tani, përsëri në klasifikim.
Pra, ne të vazhdojmë në kërkim në tjetër e elementeve.
Dhe në këtë rast, ne shohim se ka ka elemente të tjerë më pak se
strumbullar, kështu që ne të lënë ata të gjithë në anën e djathtë të murit.
Së fundi, ne kemi marrë në elementin e tanishëm dhe të shohim se ajo është strumbullar.
Tani, kjo do të thotë se ne kemi dy seksionet e array, qenien e parë
vogël në aks dhe në anën e majtë të murit, dhe të dytë që
mëdha se boshti te anën e djathtë të murit.
Ne duam të vënë elementin strumbullar mes dy, dhe pastaj ne do të dini
se strumbullar është në të drejtën e vendi përfundimtar renditura.
Pra, ne të kaloni elementin e parë mbi anën e djathtë të murit me strumbullar,
dhe ne e dimë strumbullar-së në pozitën e saj të drejtë.
>> Ne pastaj të përsëritur këtë proces për subarrays majtë dhe të djathtë të strumbullar.
Që subarray fundit është vetëm një element të gjatë, ne e dimë se tashmë
Renditur sepse si mund të jetë jashtë urdhërojë qoftë se ju jeni vetëm një element?
Për anën e djathtë të subarray, ne shohim se boshti është 5, dhe muri
ka mbetur vetëm të 6.
Dhe element aktuale gjithashtu fillon nga sa 6.
6 është kaq e madhe se 5.
Ne e lënë atë aty ku është në anën e djathtë të murit.
Tani, duke lëvizur on, 3 është më pak se 5.
Kështu ne kaluar me elementin e parë vetëm e drejtë të murit.
Tani, unë u zhvendos murin deri një.
Tani, të lëvizin për në 8.
8 është më i madh se 5, dhe kështu që ne të lënë atë.
4 është më pak se 5, ne mënyrë të kaluar atë.
Dhe në.
>> Çdo herë që përsëris procesin për anët majtë dhe të djathtë të vektorit. ne
zgjidhni një strumbullar dhe të bëjë krahasime dhe për të krijuar një nivel tjetër të majtë dhe të
subarrays drejtë.
Kjo thirrje rekursive do të vazhdojë deri kemi arritur në fund, kur ne kemi
ndanë array përgjithshëm në vetëm subarrays e gjatësisë 1.
Nga atje, ne e dimë array të zgjidhet sepse çdo element ka, në
disa pika, qenë një strumbullar.
Me fjalë të tjera, për çdo element, të gjithë numrat në të majtë janë më të vogla
vlerat dhe të gjitha numrat në drejtë kanë vlera më të mëdha.
>> Kjo metodë punon shumë mirë nëse vlera e boshtit të zgjedhur është
afërsisht në mes varg i vlerave të listave.
Kjo do të thotë se, pasi ne shkojmë elemente rreth, atje rreth sa më shumë
elementet në të majtë të strumbullar si ka në të djathtë.
Dhe natyra ndarje-dhe-Conquer e Quicksort algorithm është marrë më pas
Avantazhi plot.
Kjo krijon një Runtime të O (n log n,) n sepse ne duhet të bëjmë n minus 1
Krahasimet në çdo brez dhe log n sepse ne kemi për të ndarë të listës
log herë n.
Megjithatë, në rastet më të këqija, kjo algorithm fakt mund të jetë O (n
në katror.) Supozoni se në çdo brez, strumbullar ndodh vetëm në mënyrë që të jetë
më të vogël apo më e madhe e Numrat ne jemi klasifikim.
Kjo do të thotë thyer poshtë në listë n herë dhe duke e bërë n minus 1
Krahasimet çdo herë të vetme.
Kështu, o të n katror.
>> Si mund të përmirësohet metoda?
Një mënyrë e mirë për të përmirësuar metodën është për të shkurtuar në probabilitetin që
runtime është kurrë në të vërtetë o i N katror.
Mos harroni këtë më të keq, skenarin më të keq mund të ndodhë vetëm kur
strumbullar zgjedhur është gjithmonë më e larta ose vlera më e ulët në rrjet.
Për të siguruar këtë është më pak gjasa të ndodhë, ne mund të gjeni strumbullar nga
duke zgjedhur elemente të shumta dhe duke marrë vlerën mesatare.
>> Emri im është Mark Grozen-Smith, dhe kjo është CS50.
>> Për thjeshtësi, le të supozojmë se ata gjërat janë vetëm numra të plotë, por
e di se Quicksert -
Quicksert?
Më vjen keq.
>> Këtu ne kemi numra të plotë 6, 5, 1, 3, 8, 4, 9.
>> Gjuha 1: Really?
>> Gjuha 2: Mos të ndalemi këtu.
>> Gjuha 1: Really?