>> MARK GROZEN-SMITH: Hi, aku Mark Grozen-Smith, dan ini adalah Quicksort.
Sama seperti insertion sort dan bubble sort, Quicksort adalah algoritma untuk
menyortir daftar atau array hal.
Untuk mempermudah, mari kita asumsikan bahwa mereka hal-hal yang hanya bilangan bulat, tapi
tahu bahwa Quicksort bekerja untuk lebih dari sekedar angka.
Quickstart adalah sedikit lebih rumit dari penyisipan atau gelembung, tapi itu
juga jauh lebih efisien dalam banyak kasus.
Tunggu sebentar.
Apakah dia hanya mengatakan "sebagian besar kasus, "tidak" semua "?
Menariknya, tidak ada.
Tidak semua kasus yang sama.
Jangan khawatir tentang detail ini jika Anda belum melihat notasi O besar, tapi
Quicksort adalah O (n kuadrat) algoritma paling buruk, seperti
penyisipan atau bubble sort.
Namun, biasanya bertindak jauh lebih seperti algoritma m analog tua.
Mengapa?
Kita akan kembali nanti.
Tapi untuk saat ini, mari kita belajar bagaimana Quicksort bekerja.
>> Jadi mari kita berjalan melalui Quicksorting ini array bilangan bulat dari terkecil
ke terbesar.
Di sini kita memiliki bilangan bulat 6, 5, 1, 3, 8, 4, 7, 9, dan 2.
Pertama, kita memilih elemen terakhir dari array ini - dalam kasus ini, dua -
dan menyebutnya sebagai "poros." Selanjutnya, kita mulai melihat dua hal -
satu, indeks terendah, yang saya akan merujuk sebagai tinggal di sebelah kanan
dinding, dan, dua, paling kiri elemen, yang saya akan menelepon "saat ini
elemen. "Apa yang kami akan lakukan adalah melihat semua elemen lain, lain
dari poros, dan menempatkan semua elemen lebih kecil dari pivot ke
kiri dinding dan semua orang lebih besar dari pivot ke
kanan dinding.
Kemudian, akhirnya, kita akan menjatuhkan poros tepat di dinding itu untuk meletakkannya di antara
semua angka yang lebih kecil daripada dan semua angka yang lebih besar.
>> Jadi mari kita lakukan itu.
Angkat 2, menempatkan dinding di dimulai, dan memanggil 6 "saat ini
elemen. "Jadi kita ingin melihat elemen saat kami, 6.
Dan karena itu lebih besar dari 2, kami meninggalkannya di sana untuk
kanan dinding.
Kemudian, kita beralih ke melihat 5 sebagai kami elemen saat ini dan melihat bahwa ini
adalah, sekali lagi, lebih besar dari pivot, jadi kami meninggalkan di tempat itu adalah di sebelah kanan
sisi dinding.
Kami melanjutkan.
Elemen kami saat ini adalah sekarang 1, dan - oh.
Ini berbeda sekarang.
Elemen saat sekarang lebih kecil dari poros, jadi kami ingin meletakkannya
di sebelah kiri dinding.
Untuk melakukan hal ini, mari kita beralih elemen saat ini dengan indeks terendah
duduk tepat di sebelah kanan dinding.
Sekarang, kita bergerak dinding sampai satu indeks sehingga 1 adalah di sebelah kiri
sisi dinding sekarang.
>> Tunggu.
Aku hanya mencampur-adukkan elemen pada sisi kanan dinding, bukan?
Jangan khawatir.
Itu baik-baik saja.
Satu-satunya hal yang kita peduli untuk saat ini adalah bahwa semua elemen tersebut ke
kanan dinding lebih besar dari poros.
Tidak ada urutan yang sebenarnya diasumsikan belum.
>> Sekarang, kembali ke penyortiran.
Jadi kita lanjutkan melihat sisa elemen.
Dan dalam hal ini, kita melihat bahwa ada tidak ada unsur-unsur lain kurang dari
poros, jadi kami meninggalkan mereka semua di sisi kanan dinding.
Akhirnya, kita sampai elemen saat ini dan melihat bahwa itu adalah poros.
Sekarang, itu berarti bahwa kita memiliki dua bagian dari array, yang pertama adalah
kecil di poros dan di sisi kiri dinding, dan yang kedua adalah
lebih besar dari pivot ke sisi kanan dinding.
Kami ingin menempatkan elemen poros antara dua, dan kemudian kita akan tahu
bahwa poros dalam haknya akhir tempat diurutkan.
Jadi kita beralih elemen pertama pada sisi kanan dinding dengan poros,
dan kita tahu pivot ini dalam posisi yang tepat.
>> Kami kemudian ulangi proses ini untuk subarrays kiri dan kanan dari poros.
Karena subarray terakhir adalah satu-satunya elemen panjang, kita tahu bahwa sudah
diurutkan karena bagaimana Anda bisa keluar dari memesan jika Anda hanya satu elemen?
Untuk sisi kanan subarray, kita melihat bahwa poros adalah 5, dan dinding
hanya tersisa dari 6.
Dan elemen saat ini juga mulai keluar sebagai 6.
Jadi 6 lebih besar dari 5.
Kami meninggalkan tempat itu pada sisi kanan dinding.
Sekarang, pindah, 3 kurang dari 5.
Jadi kita beralih dengan elemen pertama tepat dari dinding.
Sekarang, aku pindah dinding sampai satu.
Sekarang, pindah ke 8.
8 lebih besar dari 5, dan jadi kami meninggalkannya.
4 kurang dari 5, jadi kita aktifkan.
Dan di.
>> Setiap kali kita ulangi proses di sisi kiri dan kanan dari array. kami
memilih pivot dan melakukan perbandingan dan menciptakan tingkat lain dari kiri dan
subarrays tepat.
Panggilan rekursif ini akan berlanjut sampai kita mencapai akhir ketika kita sudah
dibagi array keseluruhan menjadi hanya subarrays panjang 1.
Dari sana, kita tahu array diurutkan karena setiap elemen memiliki,
beberapa titik, menjadi pivot.
Dengan kata lain, untuk setiap elemen, semua angka di sebelah kiri adalah lebih rendah
nilai-nilai dan semua nomor ke benar memiliki nilai yang lebih besar.
>> Metode ini bekerja sangat baik jika nilai pivot yang dipilih adalah
kira-kira di tengah rentang nilai daftar.
Ini berarti bahwa, setelah kami pindah elemen sekitar, ada sekitar sebanyak
elemen di sebelah kiri poros karena ada di sebelah kanan.
Dan sifat membagi-dan-menaklukkan dari Algoritma Quicksort kemudian diambil
keuntungan penuh dari.
Hal ini menciptakan runtime dari O (n log n,) n karena harus kita lakukan n dikurangi 1
perbandingan pada setiap generasi dan log n karena kita harus membagi daftar
log n kali.
Namun, dalam kasus-kasus terburuk, ini Algoritma sebenarnya bisa O (n
kuadrat.) Misalkan pada setiap generasi, poros kebetulan menjadi
terkecil atau terbesar dari nomor kita penyortiran.
Ini berarti mogok daftar n kali dan pengambilan n dikurangi 1
perbandingan setiap saat.
Dengan demikian, o n kuadrat.
>> Bagaimana kita bisa meningkatkan metode?
Salah satu cara yang baik untuk meningkatkan metode ini untuk mengurangi probabilitas bahwa
runtime yang pernah benar-benar o n kuadrat.
Ingat, skenario terburuk terburuk ini hanya dapat terjadi ketika
poros yang dipilih adalah selalu yang tertinggi atau nilai terendah dalam array.
Untuk memastikan hal ini kurang mungkin terjadi, kita dapat menemukan poros dengan
memilih beberapa elemen dan mengambil nilai median.
>> Nama saya adalah Mark Grozen-Smith, dan ini adalah CS50.
>> Untuk mempermudah, mari kita asumsikan bahwa mereka hal-hal yang hanya bilangan bulat, tapi
tahu bahwa Quicksert -
Quicksert?
Maaf.
>> Di sini kita memiliki bilangan bulat 6, 5, 1, 3, 8, 4, 9.
>> SPEAKER 1: Benarkah?
>> SPEAKER 2: Jangan berhenti di situ.
>> SPEAKER 1: Benarkah?