MARK GROZEN-Smith: Szia, én vagyok Mark Grozen-Smith, és ez gyorsrendezés. Csakúgy, mint a beillesztés sort és a buborék sort, a gyors-egy algoritmus rendezés a lista, vagy egy sor dolgot. Az egyszerűség kedvéért tegyük fel, hogy ezeket a a dolgok csak egész számok, de tudják, hogy a gyors dolgozik több, mint csak számok. Ez a menüpont egy kicsit bonyolultabb mint a beillesztés vagy buborék, de is sokkal hatékonyabb a legtöbb esetben. Várj egy percet. Csak nem azt, hogy "a legtöbb esetben, a "nem" minden "? Érdekes módon, nem. Nem minden esetben azonosak. Ne aggódj ezt a részletet, ha Nem láttam a nagy O jelölés még, de Gyors-O (n négyzetes) algoritmus a legrosszabb esetben, mint beillesztés vagy bubble sort. Azonban ez általában sokkal jár mint egy régi analóg m algoritmus. Miért? Majd menj vissza később. De most, most csak tanulni hogyan gyorsrendezés elvét. 

Szóval séta Quicksorting ezt tömb egész szám legkisebb a legnagyobb. Itt van az egész 6 5, 1, 3, 8, 4, 7, 9 és 2. Először is, vedd az utolsó eleme ezt a tömböt - ebben az esetben a két - és hívja, hogy a "pivot". Következő, elkezdi nézni két dolgot - egy, a legkisebb index, amit majd hivatkozni hogy tartózkodik a jobbra a fal, és a két, a bal szélső elem, amely hívom a "jelenlegi elem. "mit fogunk csinálni a meg az összes többi elem, egyéb , mint a pivot, és tegye az összes elemet kisebb, mint az, hogy az elforduló balra a fal és minden nagyobb, mint a pivot a jobbra a falon. Aztán végül dobjuk a pivot közvetlenül a falra, hogy tedd között összes szám kisebb, mint és az összes nagyobb számok. 

Így csináljuk. Vedd fel a 2., tedd a falra a elején, és hívja a 6. a "jelenlegi elem. "Ezért szeretnénk nézni a jelenlegi elem, a 6.. És mivel ez nagyobb, mint a 2, hagyjuk ott a jobbra a falon. Aztán megyünk tovább nézni az 5, mint a mi aktuális elem, és látom, hogy ez a van, ismét, nagyobb, mint a pivot, ezért hagyja, ahol a jobb oldalon oldalán a fal. Tovább kell lépnünk. A jelenlegi elem Most 1 és - ó. Ez most más. Az aktuális elem már kisebb, mint a A pivot, ezért szeretnénk, hogy azt a bal oldalon a fal. Ehhez nézzük csak be kell kapcsolnia a aktuális elem a legalacsonyabb index ül csak jobbra a falon. Most megyünk a falnak fel egy index így az 1 a bal oldalon oldalán a fal most. 

Várjon. Én csak összekeverte az elemeket a jobb oldalon a fal, nem igaz? Ne aggódj. Ez rendben van. Az egyetlen dolog, amit érdekel most az, hogy ezeket az elemeket a a fal jobb nagyobbak mint a pivot. Nem aktuális rendelés feltételezzük még. 

Most vissza a válogatás. Tehát tovább néztem a többi elem. És ebben az esetben, azt látjuk, hogy vannak más elemeket nem kevesebb, mint a pivot, így hagyjuk őket a a jobb oldalán a fal. Végül eljutunk az aktuális elem és látom, hogy ez a pivot. Nos, ez azt jelenti, hogy a két szakaszok a tömb, az első lény kicsi a pivot és a bal oldali a fal, és a második lény nagyobb, mint a pivot a jobb oldalán a fal. Azt szeretnénk, hogy a pivot elem között A két, és akkor tudjuk, hogy hogy a pivot annak megfelelő végső rendezett helyen. Így kapcsolja az első elem a jobb oldalán a fal a pivot, és tudjuk, hogy a pivot a annak megfelelő pozícióba. 

Ezután ismételje meg ezt a folyamatot a subarrays bal és jobb a pivot. Mivel az utolsó csak egy subarray elem hosszú, tudjuk, hogy ez már rendezett, mert hogy lehet ki rendelni, ha csak az egyik eleme? A jobb oldalon a subarray, mi látni, hogy a pivot értéke 5, és a fal csak maradt a 6. És az aktuális elem is indul ki, mint a 6. Tehát 6 nagyobb, mint 5. Hagyjuk ott, ahol ez a jobb oldalán a fal. Most, mozgó, 3 kisebb, mint 5. Így kapcsolja az első elem csak jobb a fal. Most költöztem a fal fel egy. Most mozog a 8. 8 nagyobb, mint 5, és így hagyjuk. A 4 kevesebb, mint 5, úgyhogy kapcsolja. És. És. 

Minden alkalommal, amikor ismételje meg a folyamatot a bal és jobb oldalán a tömb. mi válasszon egy pivot, és nem az összehasonlítás és hozzon létre egy másik szintje a bal-és jobb subarrays. Ez a rekurzív hívás addig folytatódik, amíg elérjük a végét, amikor már felosztották a teljes tömb csak subarrays hosszúságú 1. Onnan tudjuk, hogy a tömb rendezve mert minden elem, a Valamikor volt a pivot. Más szóval, minden elem, minden A számok a bal oldalon kisebb értékek és a számokat, hogy a joga van a nagyobb érték. 

Ez a módszer nagyon jól működik, ha a értéke a pivot választott hozzávetőleg a közepén tartománya a lista értékeket. Ez azt jelenti, hogy, miután mozgunk elemek körül, ott körülbelül annyi elemeket, hogy a bal oldalon a forgócsap mint ahány jobbra. És az oszd meg és uralkodj jellege Gyors-algoritmus ezután venni teljes mértékben kihasználják. Ez létrehoz egy futásidejű O (n log n) n, mert meg kell tennünk n mínusz 1 összehasonlítások minden generáció és log n mert meg kell osztani a lista log n-szer. Azonban, a legrosszabb esetben ez algoritmus is lehet O (n négyzeten.) Tegyük fel, minden nemzedék, A pivot csak azért történik, hogy a a legkisebb, illetve a legnagyobb a számok vagyunk válogatás. Ez azt jelentené, összeomlanak a listán n-szer és a döntéshozatalban n mínusz 1 összehasonlítást minden egyes alkalommal. Így o n a négyzeten. 

Hogyan lehet javítani a módszer? Egy jó módja annak, hogy javítsák a módszer csökkenteni a valószínűségét, hogy Az üzemidő valaha is o n a négyzeten. Ne feledje, ez a legrosszabb, legrosszabb esetben csak akkor történhet meg, ha a forgócsap választott mindig a legmagasabb vagy a legalacsonyabb érték a tömbben. Annak érdekében, hogy ez a kevésbé valószínű, hogy megtörténjen, megtaláljuk a pivot a kiválasztása több elemet és figyelembe véve a medián értéket. 

A nevem Mark Grozen-Smith, és ez a CS50. 

Az egyszerűség kedvéért tegyük fel, hogy ezeket a a dolgok csak egész számok, de tudják, hogy Quicksert - Quicksert? Bocsánat. 

Itt van az egész 6, 5, 1, 3, 8, 4, 9. 

SPEAKER 1: Tényleg? 

SPEAKER 2: nem állnak meg ott. 

SPEAKER 1: Tényleg?