ŽENKLAS GROZEN-Smith: Sveiki, aš esu Pažymėti Grozen-Smith, ir tai yra QuickSort. Tiesiog kaip ir įterpimo rūšiuoti ir burbulas rūšiuoti QuickSort yra už algoritmas rūšiavimas sąrašą arba dalykų masyvo. Kad būtų paprasčiau, tarkime, kad tie viskas yra tik sveikieji skaičiai, tačiau žinau, kad QuickSort veikia daugiau nei tik numeriais. Quickstart yra šiek tiek sudėtingesnis kaip įterpimas ar burbulas, bet tai Taip pat yra daug veiksmingiau daugeliu atvejų. Palauk sekundę. Ar jis tiesiog pasakyti "labiausiai atvejai ", o ne" visi "? Įdomu tai, kad ne. Ne visi atvejai yra vienodi. Nesijaudinkite apie šį išsamiai, jei jums nemačiau didelis O notacijos nėra, tačiau QuickSort yra O (n kvadratu) algoritmas blogiausiu atveju, kaip įterpimo arba burbulas rūšiuoti. Tačiau ji paprastai veikia daug kaip senas analoginis m algoritmas. Kodėl? Mes grįžti į vėliau. Bet dabar, tegul tiesiog išmokti kaip QuickSort veikia. 

Taigi, galime eiti per Quicksorting tai sveikųjų skaičių masyvas iš mažiausių iki didžiausio. Čia mes turime skaičiais 6, 5, 1, 3, 8, 4, 7, 9, ir 2. Pirma, mes pasirinkti galutinį elementas tai masyvas - šiuo atveju, du - ir skambinti, kad "suktis". Be to, mes pradėti ieškoti dviejų dalykų - vienas, žemiausia indekso, kurį aš skaitykite kaip būna su teise siena, ir du, kairiausias elementas, kurį aš vadinu "dabartinis elementas. "Ką mes ketiname daryti yra žiūrėti visus kitus elementus, kitus nei ašies, ir įdėti visus elementus mažesnės nei iki ašies liko sienos ir visi tie, didesnis nei iki ašies teisė sienos. Tada, pagaliau, mes lašas suktis tiesiai ant tos sienos įdėti jį tarp visi skaičiai mažesni už jį ir visi numeriai didesni. 

Taigi galime daryti. Paimkite 2, įdėti siena pradžioje, ir paskambinti į 6 "dabartinė elementas. "Taigi, mes norime pažvelgti į mūsų dabartinis elementas, 6. Ir kadangi jis didesnis nei 2, mes palikti jį ten teisė sienos. Tada mes pereiti į pažvelgti į 5, nes mūsų dabartinis elementas ir pamatyti, kad tai , vėlgi, didesnis nei ašies, todėl mes palikti jį ten, kur jis yra dešinėje pusė sienos. Mes judėti pirmyn. Mūsų dabartinis elementas yra dabar 1, ir - oi. Tai kitokia. Dabartinis elementas yra dabar mažesnis nei ašis, todėl norime jį prie sienos kairėje. Norėdami tai padaryti, tegul tiesiog pereiti dabartinis elementas su mažiausiu indeksas sėdi tik prie sienos dešinėje. Dabar mes pereiti sieną iki vieno indeksas taip 1 yra kairėje pusė sienos dabar. 

Palaukti. Aš tiesiog sumaišyti ant elementų Dešinėje pusėje prie sienos, ar ne aš? Nesijaudinkite. Tai gerai. Vienintelis dalykas, mums rūpi dabar yra tai, kad visi šie elementai teisė sienos yra didesni nei ašies. Ne faktinis kad prielaida dar. 

Dabar atgal prie rūšiavimo. Taigi mes ir toliau ant žiūri elementų poilsio. Ir šiuo atveju, mes matome, kad yra nėra kitų elementų, mažiau nei ašis, todėl mes palikti juos visus Dešinėje pusėje sienos. Galiausiai, mes turime einamųjų elemento ir pamatysite, kad tai yra ašis. Dabar, tai reiškia, kad mes turime du skyriai masyvo, pirmasis būties mažas ant ašies ir kairėje pusėje sienos, o antrasis didesnis nei iki ašies Dešinėje pusėje sienos. Mes norime įdėti sukimosi elementas tarp du, ir tada mes žinome, kad ašis yra jo dešinėje galutinis surūšiuoti vieta. Taigi, mes pereiti pirmąjį elementą Dešinėje pusėje prie sienos su ašies, ir mes žinome, ašis s savo teisingoje padėtyje. 

Mes tada pakartokite šį procesą subarrays į kairę ir į dešinę nuo ašies. Kadangi paskutinis subarray yra tik vienas elementas ilgai, mes žinome, kad tai jau surikiuota, nes, kaip jūs galite būti iš užsisakyti, jei esate tik vienas elementas? Dėl dešinėje subarray, mes matyti, kad ašis yra 5, ir sienos tiesiog liko iš 6. Ir dabartinis elementas taip pat prasideda kaip 6. Taigi 6 yra didesnis nei 5. Mes palikti jį ten, kur jis yra Dešinėje pusėje sienos. Dabar pereikime prie 3 yra mažesnis nei 5. Taigi mes vėl jį su pirmojo elemento teisingai sienos. Dabar, aš persikėlė į sieną dar vieną. Dabar pereikime prie 8. 8 yra didesnis nei 5, ir todėl palikti jį. 4 yra mažesnis nei 5, tad jį įjungti. Ir. Ir. 

Kiekvieną kartą, kai mes pakartokite procesą kairysis ir dešinysis kraštai masyvo. mes pasirinkti suktis ir daryti palyginimus ir sukurti kitą lygį kairėje ir teisė subarrays. Tai grįžtamojo skambutis bus tęsiamas tol, kol mes pasiekti pabaigos, kai mes padalintas į bendrą masyvą į tik subarrays ilgio 1. Iš ten, mes žinome, masyvas surūšiuotas nes kiekvienas elementas turi ne Tam tikru momentu, buvo ašis. Kitaip tariant, kiekvieno elemento, visi į kairę skaičiai yra mažiau vertybės ir visi iki numeriai teisė turėti didesnes vertes. 

Šis metodas veikia labai gerai, jei vertė šerdeso pasirinkta maždaug per vidurį diapazonas sąrašą vertybes. Tai reikštų, kad, kai mes einame elementai aplink, yra maždaug kaip daug elementai iš ašies kairėje nes yra į dešinę. Ir skaldyk ir valdyk pobūdis QuickSort algoritmas tada imtis visiškai išnaudoti. Tai sukuria O runtime (n log n) n, nes mes turime daryti n atėmus 1 palyginimams kiekviena karta ir log n, nes mes turime padalinti sąrašą prisijunkite n kartų. Tačiau blogiausiu atveju, tai algoritmas iš tikrųjų gali būti O (n kvadratu.) Tarkime, kiekvieną kartą, suktis tiesiog taip atsitinka, kad mažiausia arba didžiausia numeriai mes rūšiavimo. Tai reikštų, skaidyti sąrašą n kartų ir padaryti n atėmus 1 lyginti kiekvieną kartą. Taigi, o n kvadratu. 

Kaip mes galime pagerinti metodas? Vienas geras būdas pagerinti metodas yra siekiama sumažinti tikimybę, kad Runtime kada nors iš tikrųjų O n kvadratu. Prisiminti šią blogiausias blogiausiu atveju gali įvykti tik tada, kai pasirinktas ašis visada yra aukščiausia arba mažiausia reikšmė masyvo. Siekiant tai užtikrinti yra mažiau tikėtina, kad taip atsitiktų, mes galime rasti suktis pagal pasirinkti kelis elementus ir atsižvelgiant medianą. 

Mano vardas yra Markas Grozen-Smith ir tai yra CS50. 

Kad būtų paprasčiau, tarkime, kad tie viskas yra tik sveikieji skaičiai, tačiau žinoti, kad Quicksert - Quicksert? Atsiprašau. 

Čia mes turime skaičiais 6, 5, 1, 3, 8, 4, 9. 

GARSIAKALBIS 1: Tikrai? 

SPEAKER 2: Negalima sustoti. 

GARSIAKALBIS 1: Tikrai?