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