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