MARK Grozen-SMITH: Hi, I Mark deyiləm -Smith Grozen və bu QuickSort edir. Just durub sort və bubble kimi sort, QuickSort üçün alqoritm Bir siyahı və ya şeyi bir sıra çeşidlənməsi. Sadəlik üçün, güman edək ki, o hər şeyi yalnız integers, lakin QuickSort üçün çalışır ki, bilirik yalnız nömrələri daha çox. Quickstart bir az daha mürəkkəbdir daha durub və ya bubble, lakin bu həmçinin daha səmərəli əksər hallarda. Ikinci gözləyin. O, yalnız "ən demək idi hallarda "deyil" bütün "? Maraqlıdır ki, no. Bütün hallarda eynidir. Bu ətraflı haqqında narahat olmayın siz əgər hələ böyük O notation gördük, amma deyil QuickSort bir O (n kvadrat) alqoritm edir ən pis halda, yalnız kimi durub və ya bubble sırala. Lakin, adətən daha çox çıxış köhnə analog m alqoritmi kimi. Niyə? Biz sonra geri almaq lazımdır. Amma indi üçün, yalnız öyrənmək bildirin QuickSort işləri necə. 

Belə ki, bu Quicksorting vasitəsilə gəzmək imkan kiçik olan integers array ən böyük. Burada biz integers 6 var 5, 1, 3, 8, 4, 7, 9, və 2. Birincisi, biz final element pick Bu array - bu halda, iki - və ki, "mil". zəng Sonra, biz iki şeyi baxmaq başlamaq - , mən istinad bilərsiniz ən aşağı index, hüququnun olma kimi divar, və, iki, leftmost Mən "cari zəng lazımdır element, element. "Biz nə olacaq edir digər bütün digər elementləri baxmaq mil daha və bütün elementləri qoymaq na mil daha kiçik divar sol və bütün bu na mil daha böyük divar hüququ. Sonra, nəhayət, biz mil düşmək lazımdır sağ arasında qoymaq üçün divar bu daha kiçik bütün nömrələri və bütün nömrələri böyük. 

Belə ki, bunu bildirin. 2-up seçin, olan divar qoymaq başlayan və 6 "cari zəng element. "Beləliklə, biz baxmaq istəyirəm bizim cari element, 6. Və bu daha çox var-ci ildən 2, biz orada onu tərk divar hüququ. Sonra, biz 5-də baxmaq üçün hərəkət bizim cari element və bax ki, bu , yenidən, mil daha böyük, belə ki, biz o, sağ olduğu onu tərk divar yan. Biz hərəkət. Bizim cari element edir indi 1, və - oh. Bu indi fərqlidir. Cari element indi daha kiçik mil, biz onu qoymaq istəyirəm divar sol. Bunu etmək üçün, yalnız keçid edək ən aşağı göstərici ilə cari element yalnız divar sağ oturan. İndi biz bir index up divar hərəkət belə ki, 1 sol indi divar yan. 

Gözləyin. Mən yalnız elementləri qarışdırılır divar sağ tərəfində, mən etmədi? Narahat olmayın. Ki, gözəl. Biz indi düşündüyüm tək şey ki, bütün bu elementlər divar sağ böyükdür mil daha. No faktiki sifariş hələ ehtimal edilir. 

İndi geri çeşidlənməsi. Beləliklə, biz baxaraq davam elementləri qalan. Və bu halda, biz var ki, bax Bu başqa elementləri az mil, belə ki, biz onları bütün tərk divar sağ. Nəhayət, biz cari element almaq və mil olduğunu görürük. İndi ki, biz iki o deməkdir ki, serialın ilk varlıq bölmələr mil və sol tərəfində kiçik divar və ikinci varlıq na mil daha böyük divar sağ. Biz arasında mil element qoymaq istəyirəm iki, sonra biz bilirsiniz mil onun hüququ var ki, final sorted yer. Beləliklə, biz ilk element keçid mil ilə divar sağ tərəfində, və biz bilirik mil nin onun sağ mövqeyində. 

Biz sonra bu prosesi təkrar subarrays sol və mil hüququ. Son subarray yalnız biridir element uzun, biz artıq bilirik sorted necə ola bilər, çünki Siz yalnız bir element əgər sifariş? Bu subarray sağ, biz mil Wall 5 və bax ki, yalnız 6 qalıb. Və cari element də 6-kimi başlayır. Belə ki, 6 5 daha böyükdür. Bu olduğu biz onu tərk divar sağ. İndi hərəkət, 3 5-dən azdır. Beləliklə, biz ilk element ilə keçid divar sağ. İndi mən bir qədər divar köçürülüb. İndi, 8 hərəkət. 8, 5 daha çox və biz onu buraxın. 4 az 5, belə ki, biz onu yandırın. Və. Və. 

Biz prosesi təkrar Hər dəfə Serialın sol və sağ tərəf. biz bir mil seçin və müqayisə etmək və sol bir səviyyədə yaratmaq və sağ subarrays. Bu recursive zəng qədər davam edəcək biz var zaman sona çatmaq daxil ümumi array up bölünür uzunluğu 1 yalnız subarrays. Oradan, biz array çeşidlənir bilirik hər element, çünki at bəzi point, bir mil olmuşdur. Başqa sözlə, hər bir element üçün, bütün sol ədəd az var dəyərlər və bütün nömrələri sağ böyük dəyərləri var. 

Bu üsul çox yaxşı işləyir, əgər seçilmiş fırlanma dəyəri təxminən ortasında siyahısı dəyərlərin üçündür. Biz hərəkət sonra bu, o deməkdir ki, kimi bir çox haqqında orada ətrafında elementləri, mil sol elementləri sağ var kimi. Və bu parçala və fəth təbiət QuickSort alqoritmi sonra qəbul edilir tam üstünlüyü. Bu O bir uzunluğu yaradır (n n log) biz nə üçün n minus 1 n çünki hər nəsil və log müqayisələr Biz siyahısı bölmək üçün n çünki n dəfə daxil. Lakin, ən pis hallarda, bu alqoritm həqiqətən O (n ola bilər kvadrat.) hər nəsil haqqında düşünək, mil yalnız belə ola olur kiçik və ya ən böyük biz çeşidlənməsi edirik ədəd. Bu siyahısını parçalayaraq deməkdir dəfə və edilməsi n minus 1 n müqayisələri hər bir zaman. Belə ki, n o kvadrat. 

Biz necə üsul inkişaf edə bilər? Üsulu yaxşılaşdırılması üçün yaxşı bir yoldur ehtimalı azaltmaq üçün uzunluğu heç əslində n o kvadrat. Bu pis, ən pis halda ssenari saxla yalnız baş verə bilər zaman seçilmiş mil həmişə ən yüksək və ya serialın ən aşağı dəyəri. Bu nə az ehtimal təmin etmək üçün, biz mil tapa bilərsiniz çox elementləri və seçilməsi orta dəyər alaraq. 

My name Mark Grozen-Smith edir və bu CS50 edir. 

Sadəlik üçün, güman edək ki, o hər şeyi yalnız integers, lakin ki Quicksert bilirik - Quicksert? Üzr istəyirik. 

Burada integers var 6, 5, 1, 3, 8, 4, 9. 

HOPARLÖR 1: Həqiqətən? 

HOPARLÖR 2: orada dayandırmaq etməyin. 

HOPARLÖR 1: Həqiqətən?