Sorting dengan Metode Quick Sort

Quick Sort sebenarnya sama seperti Merge sort yaitu menggunakan metode Divide & Conquer. Prinsip dalam algoritma quicksort sebagai berikut:
  1. Bila elemen dalam array kurang dari jumlah tertentu (biasanya 2), proses selesai.
  2. Ambil sebuah elemen yang berfungsi sebagai poros. 
  3. Pisahkan array dalam 2 bagian, sebelah kiri lebih kecil dari poros, sebelah kanan lebih besar dari poros.
  4. Ulangi proses secara rekursif pada tiap-tiap bagian.
Hal penting dari hal algoritma ini adalah: bagaimana memilih poros dengan tepat dan secara efisien mengatur tiap-tiap elemen sehingga didapat elemen kecil > poros > elemen besar dalam kondisi (mendekati) seimbang.
Contoh Quick sort dalam gambar

Contoh Pseudocode Quick Sort 
Quicksort(A as array, low as int, high as int) 
if (low < high) 
pivot_location = Partition(A,low,high) 
Quicksort(A,low, pivot_location - 1) 
Quicksort(A, pivot_location + 1, high) 
Partition(A as array, low as int, high as int) 
pivot = A[low] leftwall = low for i = low + 1 to high 
if (A[i] < pivot) 
then leftwall = leftwall + 1 swap(A[i], A[leftwall]) swap(A[low],A[leftwall]) 
return (leftwall)
Program selengkapnya ada disini (menggunakan Java)

3 Comments

  1. Subhi AththabraniNovember 11, 2014 at 8:45 PM

    maksud dari pivot value itu apa ya?

    ReplyDelete
    Replies
    1. dinda-dinhoNovember 11, 2014 at 9:31 PM

      nilai poros yang digunakan sebagai patokan lebih besar atau lebih kecil, kalau dalam animai yang warna hitam

      Delete
  2. UnknownMay 17, 2015 at 7:42 PM

    mas cara nentuin pivot gimana ya?
    ada contoh program nya gak . . thxs

    ReplyDelete