Pengurutan Cepat dan Penerapannya · Pelajaran 8 dari 10
Quick sort
10 menit baca · BelajarCode
Quick sort juga memakai divide and conquer, tetapi dengan cara berbeda:
- Pilih satu data sebagai pivot.
- Partisi: pisahkan data menjadi yang lebih kecil dari pivot dan yang lebih besar.
- Urutkan kedua bagian dengan quick sort, lalu gabungkan: kecil, pivot, besar.
Versi yang mudah dibaca
1def quick_sort(data):2 if len(data) <= 1:3 return data4 pivot = data[len(data) // 2]5 kecil = [x for x in data if x < pivot]6 sama = [x for x in data if x == pivot]7 besar = [x for x in data if x > pivot]8 return quick_sort(kecil) + sama + quick_sort(besar)910print(quick_sort([33, 10, 55, 71, 29, 3, 18, 42]))[3, 10, 18, 29, 33, 42, 55, 71]
Versi ini jelas, tetapi membuat banyak list baru. Versi yang dipakai dalam praktik mempartisi di tempat tanpa list tambahan.
Partisi di tempat
1def partisi(data, rendah, tinggi):2 pivot = data[tinggi]3 i = rendah4 for j in range(rendah, tinggi):5 if data[j] < pivot:6 data[i], data[j] = data[j], data[i]7 i += 18 data[i], data[tinggi] = data[tinggi], data[i]9 return i1011def quick_sort_di_tempat(data, rendah=0, tinggi=None):12 if tinggi is None:13 tinggi = len(data) - 114 if rendah < tinggi:15 p = partisi(data, rendah, tinggi)16 quick_sort_di_tempat(data, rendah, p - 1)17 quick_sort_di_tempat(data, p + 1, tinggi)1819angka = [33, 10, 55, 71, 29, 3, 18, 42]20quick_sort_di_tempat(angka)21print(angka)[3, 10, 18, 29, 33, 42, 55, 71]
Fungsi partisi memindahkan semua data yang lebih kecil dari pivot ke bagian kiri, lalu menaruh pivot tepat setelahnya. Posisi pivot itu sudah final.
Analisis
- Rata-rata: O(n log n), dan dalam praktik sering lebih cepat dari merge sort karena tidak butuh memori tambahan.
- Terburuk: O(n²), terjadi jika pivot selalu data terkecil atau terbesar. Pada versi di atas yang memakai data terakhir sebagai pivot, ini terjadi ketika data sudah urut.
- Solusinya: pilih pivot secara acak, atau ambil median dari data pertama, tengah, dan terakhir.
- Tidak stabil pada versi di tempat.
Cek pemahaman
Kapan quick sort dengan pivot data terakhir menjadi paling lambat?
Latihan
Pivot acak
Ubah fungsi partisi supaya sebelum memartisi, sebuah posisi acak dipilih dan datanya ditukar dengan data terakhir. Uji pada data yang urut terbalik list(range(10, 0, -1)), salah satu susunan yang membuat versi pivot terakhir menjadi lambat.
Pembahasan
1import random23def partisi_acak(data, rendah, tinggi):4 k = random.randint(rendah, tinggi)5 data[k], data[tinggi] = data[tinggi], data[k]6 pivot = data[tinggi]7 i = rendah8 for j in range(rendah, tinggi):9 if data[j] < pivot:10 data[i], data[j] = data[j], data[i]11 i += 112 data[i], data[tinggi] = data[tinggi], data[i]13 return i1415def quick_sort_acak(data, rendah=0, tinggi=None):16 if tinggi is None:17 tinggi = len(data) - 118 if rendah < tinggi:19 p = partisi_acak(data, rendah, tinggi)20 quick_sort_acak(data, rendah, p - 1)21 quick_sort_acak(data, p + 1, tinggi)2223random.seed(3)24angka = list(range(10, 0, -1))25print("Sebelum:", angka)26quick_sort_acak(angka)27print("Sesudah:", angka)Sebelum: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] Sesudah: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Dengan pivot acak, tidak ada susunan data tertentu yang selalu membuat quick sort lambat. Kasus terburuk masih mungkin, tetapi peluangnya sangat kecil.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.