Quick Sort dan Pemilihan Pivot
Bangun quick sort dengan skema partisi Lomuto dan Hoare, bahas kasus terburuk O(n²), serta cara pemilihan pivot acak menguranginya.
Quick Sort dan Pemilihan Pivot adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Pengurutan Cepat: Bagi-dan-Taklukkan di Tempat
Pengurutan cepat adalah algoritme pengurutan yang paling banyak digunakan dalam praktik. Berbeda dari pengurutan gabung, algoritme ini mengurutkan di tempat tanpa mengalokasikan larik tambahan. Gagasan utamanya: pilih sebuah elemen poros, lakukan partition pada larik sehingga semua elemen yang lebih kecil daripada poros berada sebelum poros dan semua elemen yang lebih besar berada sesudahnya, lalu urutkan setiap partisi secara rekursif. Langkah partition membutuhkan waktu O(n), dan dengan poros yang baik, kedalaman rekursinya adalah O(log n).
def quick_sort(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
pivot_idx = partition(arr, lo, hi)
quick_sort(arr, lo, pivot_idx - 1) # sort left
quick_sort(arr, pivot_idx + 1, hi) # sort right
def partition(arr, lo, hi):
pivot = arr[hi] # Lomuto: choose last element as pivot
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Skema Partition Lomuto
Partition Lomuto menggunakan elemen terakhir sebagai poros. Penunjuk lambat i melacak batas wilayah ‘lebih kecil dari poros’; penunjuk cepat j melakukan pemindaian ke arah depan. Ketika arr[j] <= pivot, naikkan i dan tukarkan arr[i] dengan arr[j], sehingga wilayah elemen kecil meluas. Setelah pemindaian selesai, tempatkan poros di i+1 dengan menukarnya dengan arr[hi]. Implementasinya sederhana, tetapi melakukan pertukaran 3× lebih banyak daripada skema Hoare.
def lomuto_partition_traced(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
print(f'Pivot: {pivot}, array: {arr[lo:hi+1]}')
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
print(f'After partition: {arr[lo:hi+1]}')
return i + 1
arr = [3, 1, 4, 1, 5, 9, 2, 6]
lomuto_partition_traced(arr, 0, len(arr)-1)Skema Partition Hoare
Partition Hoare menggunakan dua penunjuk yang dimulai dari kedua ujung dan bergerak ke dalam hingga berpapasan. Skema ini memilih poros (biasanya elemen pertama), lalu memindahkan elemen yang lebih kecil daripada poros ke kiri dan yang lebih besar ke kanan. Skema Hoare melakukan pertukaran 3× lebih sedikit daripada Lomuto dan bekerja lebih baik dengan elemen yang sama, tetapi poros tidak berakhir di posisi finalnya setelah partition — sehingga memerlukan pemanggilan rekursif yang sedikit berbeda.
def hoare_partition(arr, lo, hi):
pivot = arr[lo] # first element as pivot
i, j = lo - 1, hi + 1
while True:
i += 1
while arr[i] < pivot: i += 1
j -= 1
while arr[j] > pivot: j -= 1
if i >= j: return j
arr[i], arr[j] = arr[j], arr[i]
def quick_sort_hoare(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
p = hoare_partition(arr, lo, hi)
quick_sort_hoare(arr, lo, p) # note: p not p-1
quick_sort_hoare(arr, p+1, hi)
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_hoare(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Kasus Terburuk O(n²): Masukan yang Sudah Terurut
Kasus terburuk pengurutan cepat terjadi ketika poros selalu menjadi elemen terkecil atau terbesar dalam partisi. Dengan poros elemen terakhir dari Lomuto pada larik yang sudah terurut, partition selalu menempatkan 0 elemen di kiri dan n-1 elemen di kanan: pohon rekursi merosot menjadi rantai dengan kedalaman n, sehingga menghasilkan O(n²) perbandingan. Inilah alasan pemilihan poros sangat penting dan mengapa implementasi produksi mengacak poros.
import sys
sys.setrecursionlimit(5000)
def quick_sort_naive(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
comparisons = [0]
def _qs(lo, hi):
if lo >= hi: return
pivot = arr[hi] # last element pivot
i = lo - 1
for j in range(lo, hi):
comparisons[0] += 1
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
_qs(lo, p-1); _qs(p+1, hi)
_qs(lo, hi)
return comparisons[0]
import math
n = 100
sorted_arr = list(range(n))
ops = quick_sort_naive(sorted_arr)
print(f'n={n}, ops={ops}, n^2={n**2}') # ops close to n*(n-1)/2Poros Acak: O(n log n) yang Diharapkan
Dengan memilih poros secara acak dan seragam (tukar elemen acak dengan arr[hi] sebelum melakukan partition), probabilitas untuk terus-menerus memilih poros yang buruk turun secara eksponensial. Jumlah perbandingan yang diharapkan adalah 2n ln(n) ≈ 1.39 n log₂(n), sehingga menghasilkan waktu yang diharapkan O(n log n) dengan probabilitas yang sangat tinggi. Inilah alasan pengurutan cepat acak digunakan dalam praktik — algoritme ini menghindari kasus terburuk patologis yang dapat direkayasa lawan untuk strategi dengan poros tetap.
import random
def quick_sort_random(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
# Randomise pivot
rand_i = random.randint(lo, hi)
arr[rand_i], arr[hi] = arr[hi], arr[rand_i]
# Lomuto partition with last element as pivot
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
quick_sort_random(arr, lo, p - 1)
quick_sort_random(arr, p + 1, hi)
arr = list(range(100, 0, -1)) # worst case for naive
quick_sort_random(arr)
print(arr[:10]) # [1,2,3,4,5,6,7,8,9,10]Poros Median dari Tiga
Strategi poros lainnya: pilih median dari elemen pertama, tengah, dan terakhir. Strategi ini menghindari perilaku kasus terburuk pada masukan yang terurut atau terurut terbalik (masukan lawan yang paling umum), sekaligus menghindari biaya pembuatan bilangan acak. Banyak implementasi produksi menggunakan median-dari-tiga atau ninther (median dari tiga median) untuk larik besar dan menggunakan pengurutan penyisipan sebagai cadangan untuk sublarik kecil di bawah ambang sekitar 10 elemen.
def median_of_three(arr, lo, hi):
mid = (lo + hi) // 2
# Sort lo, mid, hi values in place
if arr[lo] > arr[mid]: arr[lo], arr[mid] = arr[mid], arr[lo]
if arr[lo] > arr[hi]: arr[lo], arr[hi] = arr[hi], arr[lo]
if arr[mid] > arr[hi]: arr[mid], arr[hi] = arr[hi], arr[mid]
# Median is now at arr[mid]; swap to arr[hi-1] as pivot
arr[mid], arr[hi] = arr[hi], arr[mid]
return arr[hi] # pivot value
arr = [3, 9, 1]
print(median_of_three(arr, 0, 2), arr) # 3, [1,3,9] (sorted)Bendera Nasional Belanda: Partition Tiga Arah
Partition standar menempatkan elemen yang lebih kecil daripada poros di kiri dan yang lebih besar di kanan, tetapi elemen yang sama dengan poros tersebar. Partition tiga arah (bendera nasional Belanda) membuat tiga wilayah: <poros, ==poros, >poros. Hal ini sangat penting untuk larik dengan banyak duplikat — pada kondisi tersebut, pengurutan cepat standar menurun hingga O(n²), sedangkan pengurutan cepat tiga arah menghasilkan O(n) untuk masukan yang semua nilainya sama.
def three_way_partition(arr, lo, hi):
pivot = arr[lo]
lt = lo # arr[lo..lt-1] < pivot
gt = hi # arr[gt+1..hi] > pivot
i = lo # current
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1; i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1 # don't advance i
else:
i += 1
return lt, gt # pivot occupies arr[lt..gt]
arr = [3, 1, 4, 1, 5, 9, 2, 6, 3, 3]
lt, gt = three_way_partition(arr, 0, len(arr)-1)
print(arr, '| pivot region:', lt, 'to', gt)Quickselect: Elemen Terkecil ke-K dalam O(n)
Quickselect menggunakan langkah partition dari pengurutan cepat untuk menemukan elemen terkecil ke-k dalam waktu rata-rata O(n) tanpa mengurutkan seluruh data. Setelah partition, poros berada di posisi finalnya, p. Jika p == k, kembalikan arr[p]. Jika k < p, lakukan rekursi pada partisi kiri; jika k > p, lakukan rekursi pada partisi kanan. Secara rata-rata, setiap rekursi membagi dua masalah: O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n).
import random
def quickselect(nums, k):
'''Find kth smallest (0-indexed) in O(n) average.'''
def _select(lo, hi):
if lo == hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]
i = lo - 1
for j in range(lo, hi):
if nums[j] <= pivot:
i += 1; nums[i], nums[j] = nums[j], nums[i]
p = i + 1
nums[p], nums[hi] = nums[hi], nums[p]
if p == k: return nums[p]
elif k < p: return _select(lo, p - 1)
else: return _select(p + 1, hi)
return _select(0, len(nums) - 1)
print(quickselect([3,2,1,5,6,4], 1)) # 2 (2nd smallest)Kompleksitas Ruang Pengurutan Cepat
Pengurutan cepat disebut ‘di tempat’, tetapi menggunakan ruang tumpukan rata-rata O(log n) untuk rekursi (satu bingkai per tingkat pohon rekursi). Dalam kasus terburuk, kedalaman tumpukannya adalah O(n). Untuk menjamin ruang tumpukan kasus terburuk O(log n), selalu lakukan rekursi pada partisi yang lebih kecil terlebih dahulu dan gunakan optimisasi pemanggilan ekor untuk partisi yang lebih besar. Batas rekursi Python membuat rekursi pengurutan cepat yang sangat dalam berisiko — hal ini layak disebutkan dalam wawancara.
def quick_sort_optimised(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
while lo < hi:
p = lomuto_partition_qs(arr, lo, hi)
# Recurse on smaller partition; iterate on larger
if p - lo < hi - p:
quick_sort_optimised(arr, lo, p - 1)
lo = p + 1 # tail-call elimination
else:
quick_sort_optimised(arr, p + 1, hi)
hi = p - 1
def lomuto_partition_qs(arr, lo, hi):
pivot = arr[hi]; i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot: i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1Membandingkan Algoritme Pengurutan
Gabungkan pengetahuan Anda:
- Pengurutan cepat: O(n log n) yang diharapkan, kasus terburuk O(n²), ruang O(log n), tidak stabil, paling cepat dalam praktik untuk data acak
- Pengurutan gabung: O(n log n) yang dijamin, ruang O(n), stabil, terbaik untuk daftar tertaut dan pengurutan eksternal
- Pengurutan heap: O(n log n) yang dijamin, ruang O(1), tidak stabil, lebih lambat dalam praktik karena banyak akses yang tidak menemukan data di cache
- Pengurutan penyisipan: kasus terbaik O(n), ideal untuk n kecil atau data yang hampir terurut
# Python's sorted() uses Timsort:
# - Hybrid: merge sort for large runs, insertion sort for small (< 64 elements)
# - Stable, O(n log n) worst case
# - O(n) best case for sorted/reverse-sorted/nearly-sorted
# - O(n) extra space
import random
arr = random.sample(range(10000), 1000)
sorted_arr = sorted(arr) # Timsort
print(sorted_arr[:5], '...') # first 5 elementsIntrosort: Menggabungkan Ketiganya
Introsort (digunakan dalam C++ STL std::sort) menggabungkan pengurutan cepat, pengurutan heap, dan pengurutan penyisipan: mulai dengan pengurutan cepat acak; jika kedalaman rekursi melebihi 2 log n (yang menunjukkan rangkaian poros yang buruk), beralihlah ke pengurutan heap untuk menjamin O(n log n); gunakan pengurutan penyisipan untuk sublarik yang lebih kecil dari 16 elemen. Dengan demikian, algoritme ini memberikan kasus terburuk O(n log n), kecepatan kasus rata-rata pengurutan cepat, dan efisiensi pengurutan penyisipan untuk sublarik kecil.
# Introsort hybrid (simplified)
def introsort(arr, depth_limit=None):
if depth_limit is None:
import math
depth_limit = 2 * int(math.log2(len(arr) + 1)) if arr else 0
if len(arr) <= 16:
# insertion sort for small arrays
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1
arr[j+1] = key
return arr
if depth_limit == 0:
arr.sort() # fall back to heapsort equivalent
return arr
# Otherwise quick sort
pivot = arr[-1]
small = [x for x in arr[:-1] if x <= pivot]
large = [x for x in arr[:-1] if x > pivot]
return introsort(small, depth_limit-1) + [pivot] + introsort(large, depth_limit-1)
print(introsort([5,3,8,1,9,2,7]))Uji Cepat
Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini, Anda mempelajari: pengurutan cepat melakukan partition di tempat di sekitar poros dan melakukan rekursi pada setiap sisi, sehingga mencapai waktu yang diharapkan O(n log n) dengan ruang tumpukan O(log n) — lebih cepat dalam praktik daripada pengurutan gabung untuk data acak, kasus terburuk O(n²) terjadi pada masukan yang terurut dengan poros tetap dan dihindari melalui pemilihan poros acak atau median-dari-tiga, dan partition tiga arah menangani elemen duplikat secara efisien, sedangkan quickselect memperluas gagasan partition untuk menemukan elemen terkecil ke-k dalam waktu rata-rata O(n) tanpa pengurutan penuh. Selanjutnya, kita akan menjelajahi pengurutan non-perbandingan dan sort bawaan Python.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Quick Sort dan Pemilihan Pivot” gratis?
Ya — teks lengkap “Quick Sort dan Pemilihan Pivot” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Quick Sort dan Pemilihan Pivot”?
Bangun quick sort dengan skema partisi Lomuto dan Hoare, bahas kasus terburuk O(n²), serta cara pemilihan pivot acak menguranginya. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “Quick Sort dan Pemilihan Pivot” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Bubble Sort dan Insertion Sort
- Merge Sort: Bagi, Urutkan, Gabungkan
- Quick Sort dan Pemilihan Pivot
- Pengurutan Tanpa Perbandingan dan sort() Python