Python DSALesson 108Preview gratis
Quick Sort
Lesson ini bagian dari Python · Semua level
Ringkasan
Pelajaran ini membahas Quick Sort, algoritma divide and conquer yang memilih sebuah pivot lalu memisahkan data menjadi dua kelompok, yaitu lebih kecil dan lebih besar dari pivot. Masing-masing kelompok kemudian diurutkan secara rekursif. Dengan pivot yang baik, quick sort bekerja rata-rata O(n log n) dan termasuk algoritma pengurutan tercepat untuk data besar.
Poin kunci
- Langkah quick sort: pilih pivot, partisi data, lalu urutkan dua bagian secara rekursif.
- Rata-rata O(n log n), namun kasus terburuk O(n^2) jika pivot selalu elemen paling ekstrem.
- Pemilihan pivot bisa elemen pertama, tengah, atau kombinasi ketiganya (median of three).
- Versi dengan list comprehension sederhana tetap membutuhkan memori tambahan O(n).
- Quick sort umumnya stabil, tetapi sangat cepat dalam praktiknya karena cache-friendly.
Materi lengkap
Contoh kode dan kuis
Materi lengkap, contoh kode, dan kuis tersedia untuk pelanggan. 5 soal.