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ë. 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?