Quick Sort

Algoritma divide-and-conquer yang memilih pivot, mempartisi elemen di sekitarnya, lalu mengurutkan setiap partisi secara rekursif.

Kompleksitas

Waktu (Terbaik)

O(n log n)

Waktu (Rata-rata)

O(n log n)

Waktu (Terburuk)

O(n²)

Memori

O(log n)

Poin Penting

›Rata-rata O(n log n) dengan konstanta sangat kecil, paling cepat dalam praktik untuk sebagian besar input
›Kasus terburuk O(n²) terjadi pada input yang sudah terurut atau terbalik dengan pilihan pivot yang buruk
›Pivot acak atau strategi median-of-three mencegah kasus terburuk
›In-place: hanya butuh ruang stack O(log n) dari rekursi
›Secara default tidak stable; dipakai di sebagian besar implementasi sort pada standard library

Visualizer Interaktif

Langkah 0 / 0✓ Selesai diurutkan!

LambatCepat

NormalDibandingkanDitukarTerurut

Contoh Kode

Swift

func quickSort(_ arr: inout [Int], _ low: Int, _ high: Int) {
    guard low < high else { return }
    let pi = partition(&arr, low, high)
    quickSort(&arr, low, pi - 1)
    quickSort(&arr, pi + 1, high)
}

func partition(_ arr: inout [Int], _ low: Int, _ high: Int) -> Int {
    let pivot = arr[high]
    var i = low - 1
    for j in low..<high {
        if arr[j] <= pivot { i += 1; arr.swapAt(i, j) }
    }
    arr.swapAt(i + 1, high)
    return i + 1
}

var nums = [10, 7, 8, 9, 1, 5]
quickSort(&nums, 0, nums.count - 1)
print(nums)  // [1, 5, 7, 8, 9, 10]

Latihan Soal

Kth Largest Element in an Array

SedangLeetCode ↗

Sort an Array

SedangLeetCode ↗

Wiggle Sort II

SedangLeetCode ↗