QUICK SORT dan IMPLEMENTASI

Quicksort ditemukan oleh C.A.R Hoare.  Seperti pada merge sort, algoritma ini juga
berdasar pada pola divide-and-conquer. Berbeda dengan  merge sort, algoritma  ini
hanya mengikuti langkah – langkah sebagai berikut :


1. Divide
Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r]
dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q]
dan  setiap   elemen  pada A[q+1…r]   adalah  lebih  besar   atau  sama  dengan
elemen  pada  A[q].  A[q]   disebut   sebagai   elemen   pivot.   Perhitungan  pada
elemen q merupakan salah satu bagian dari prosedur pemisahan.

2. Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif
Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi
pengurutan elemen – elemen pada sub-array


Algoritma :

void quickSort(Object array[], int leftIdx, int rightIdx) {
int pivotIdx;
/* Kondisi Terminasi */
if (rightIdx > leftIdx) {
pivotIdx = partition(array, leftIdx, rightIdx);
quickSort(array, leftIdx, pivotIdx-1);
quickSort(array, pivotIdx+1, rightIdx);
}
}

Contoh Program :
package Praktikum_4;

/**
 *
 * @author Angga
 */
public class QuickSort {
    public static void quick_srt(int array[],int low, int n){
    int lo = low;
    int hi = n;
    if (lo >= n) {
      return;
    }
    int mid = array[(lo + hi) / 3];
    while (lo < hi) {
      while (lo< mid) {
        lo++;
      }
      while (lo mid) {
        hi--;
      }
      if (lo < hi) {
        int T = array[lo];
        array[lo] = array[hi];
        array[hi] = T;
      }
    }
    if (hi < lo) {
      int T = hi;
      hi = lo;
      lo = T;
    }
    quick_srt(array, low, lo);
    quick_srt(array, lo == low ? lo+1 : lo, n);
  }

public static void main(String a[]){
    int i;
    int array[] = {12,9,4,99,120,1,3,10,13};
    System.out.println("=====================================");
    System.out.println("Nilai Sebelum Diurutkan");
    System.out.println("=====================================");
    for(i = 0; i < array.length; i++)
      System.out.print( array[i]+"  ");
    System.out.println();
    quick_srt(array,0,array.length-1);
    System.out.print("Nilai Setelah Diurutkan :\n");
    for(i = 0; i
      System.out.print(array[i]+"  ");
    System.out.println();
    System.out.println("Selesai");
  }
}