QuickSort

QuickSort adalah salah satu algoritma pengurutan (sorting algorithm) yang sangat populer karena efisiensinya. Walaupun sedikit lebih kompleks, namun algoritma QuickSort sangat cocok untuk mengurutkan data dalam sebuah array yang memiliki jumlah elemen yang sangat banyak (yang akan membutuhkan waktu yang jauh lebih lama jika diurutkan dengan algoritma pengurutan sederhana semacam BubbleSort)

Algoritma QuickSort diciptakan pertama kali pada tahun 1960 oleh  C.A.R. Hoare, seorang ilmuwan Computer Science berkebangsaan Inggris yang waktu itu masih seorang mahasiswa tamu di Moscow State University, Uni Soviet. Algoritma ini adalah algoritma rekursif yang bekerja dengan prinsip divide and conquer, adapun logikanya adalah sebagai berikut:

  1. Pilihlah elemen tengah dalam array untuk dijadikan pembanding (biasanya disebut pivot). Elemen-elemen antara index awal sampai pivot disebut “sub array bawah” sedangkan elemen-elemen antara pivot sampai index akhir disebut “sub array atas”
  2. Bandingkan elemen-elemen dalam array dengan pivot, tukarlah posisi elemen sehingga semua elemen yang lebih kecil daripada pivot diletakkan sebelum pivot (di dalam sub array bawah) dan semua elemen yang lebih besar daripada pivot diletakkan di setelah pivot (di dalam sub array atas). Urutan data antar elemen di dalam masing-masing sub array belum harus terurut.
  3. Ulangi proses 1 dan 2 secara rekursif sehingga semakin lama ukuran sub array atas dan sub array bawah semakin kecil dan akhirnya seluruh elemen terurut dengan sempurna

Berikut ini adalah contoh procedure yang mengimplementasikan algoritma QuickSort dalam VB.NET:

Sub QuickSort(arr() As String, idx_awal As Long, idx_akhir As Long)
  Dim i As Long
  Dim j As Long
  Dim pivot As String
  Dim temp As String
  i = idx_awal
  j = idx_akhir
  'memilih elemen pivot (pembanding)
  pivot = arr((idx_awal + idx_akhir) / 2)
  Do While (i <= j)
    'cari elemen di sub array bawah yang lebih besar daripada pivot
    Do While (arr(i) < pivot And i < idx_akhir)
      i = i + 1
    Loop
    'cari elemen di sub array atas yang lebih kecil daripada pivot
    Do While (pivot < arr(j) And j > idx_awal)
      j = j - 1
    Loop
    'tukar posisinya
    If (i <= j) Then
      temp = arr(i)
      arr(i) = arr(j)
      arr(j) = temp
      i = i + 1
      j = j - 1
    End If
  Loop
  'sorting sub array bawah (rekursif)
  If (idx_awal < j) Then QuickSort arr, idx_awal, j
  'sorting sub array atas (rekursif)
  If (i < idx_akhir) Then QuickSort arr, i, idx_akhir
End Sub

Saya sendiri pertama mengenal dan menggunakan QuickSort pada tahun 2005 pada saat saya sedang mengerjakan Proyek Akhir (PA) tentang text indexing dengan inverted files. Saat itu saya membutuhkan sebuah algoritma pengurutan yang cocok untuk mengurutkan data dalam array of string dengan ukuran yang sangat besar (sekitar 100 ribu elemen). Setelah searching di perpustakaan dan internet akhirnya saya menemukan artikel tentang QuickSort. Adapun untuk keperluan proses pencarian data dalam array berukuran sangat besar itu, saya menggunakan algoritma Binary Search.

Bahkan sampai sekarang, dalam pengerjaan tugas-tugas kuliah maupun thesis, saat saya memerlukan algortima untuk melakukan operasi pengurutan dan pencarian data dalam sebuah array, QuickSort dan BinarySearch masih menjadi andalan saya 🙂

Sumber gambar:  http://en.wikipedia.org/wiki/File:Sorting_quicksort_anim.gif
Iklan

5 pemikiran pada “QuickSort

  1. bro, ini postingan awesome bgt.
    apalagi gambar visualisasinya…

    klo boleh request, tolong sekalian di compare dengan model yg lain 😀
    sy biasa pake bubble sort (soale paling mudah logika nya) 😀

    1. tengkyu so much pan, syukurlah klo ada manfaatnya. Ya, request ditampung. Sebenernya banyak banget postingan tentang programming yg pengen kutulis, nanti dikit2 dicicil, he3 😀

    1. Jangan diangkat Pit, tapi dibaca dan dipahami, hehehe…

      btw klo seorang Fitri Susanti saja merasa berat berarti penjelasanku susah dipahami dunk ya? hmmm… lain kali nulisnya harus lebih “reader friendly” nih, thx masukannya pit 😉

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s