Algoritma Quick Sort

Algoritma quick sort adalah algoritma pengurutan yang menggunakan proses pemisahan (partitioning) berdasarkan suatu nilai pembatas (pivot) secara berulang-ulang hingga suatu untaian nilai menjadi terurut.

Mekanisme kerja quicksort

Serupa dengan merge sort, algoritma quick sort juga termasuk dalam kategori divide and conquer dan bekerja secara rekursif. Perbedaannya, quicksort menggunakan proses partitioning untuk menghasilkan elemen yang terurut.

Partitioning

Partitioning adalah sebuah proses untuk membuat sebuah untaian nilai terpisah berdasarkan suatu nilai yang ditetapkan sebagai pembatas (pivot). Hasil dari proses ini adalah seluruh elemen yang nilainya lebih kecil dari pivot ada pada sisi yang berlawanan dengan nilai yang lebih besar dari pivot.

Jalankan kode berikut untuk dapat lebih memahami makna dari partitioning.

Pada contoh di atas, dilakukan partitioning dengan pivot yang dipilih dari awal elemen (angka 5). Perhatikan bahwa setelah partitioning, seluruh angka yang lebih kecil dari 5 berpindah ke sisi kiri dan sebaliknya. Pada proses ini, tidak ada jaminan bahwa elemen di kanan maupun kiri pivot terurut.

Rekursif

Selain memisah posisi elemen berdasarkan pembatasnya, perhatikan bahwa fungsi partition pada contoh kode di atas mengembalikan posisi pivot setelah pemisahan selesai. Pada algoritma quick sort, proses partitioning kemudian dipanggil dua kali lagi, untuk untaian nilai yang ada di sebelah kanan dan untuk untaian nilai yang ada di sebelah kiri (baris 5 dan 6). Hal ini dilakukan berulang-ulang hingga hanya tersisa satu elemen untuk dipartisi, yang tentunya sudah tidak diperlukan lagi (baris 2).

Berikut adalah cuplikan kodenya

def quicksort(l, bwh, atas):
  if atas <= bwh:
    return
  q = partition(l, bwh, atas)
  quicksort(l, bwh, q-1)
  quicksort(l, q, atas)
  return l

Berikut adalah source code lengkap untuk algoritma quick sort dalam bahasa pemrograman python.

Semoga bermanfaat,

Salam

Series Navigation

<< Algoritma Merge Sort