07 December 2009

Quick sort in java

Quick sort algorithm is developed by C. A. R. Hoare. Quick sort is a comparison sort. The working of quick sort algorithm is depending on a divide-and-conquer strategy. A divide and conquer strategy is dividing an array into two sub-arrays. Quick sort is one of the fastest and simplest sorting algorithm. The complexity of quick sort in the average case is Θ(n log(n)) and in the worst case is Θ(n2).

Working of quick sort algorithm:
Input:12 9 4 99 120 1 3 10 13



Output:1 3 4 10 12 13 99 120
The code of the program :

public class QuickSort{
  public static void main(String a[]){
    int i;
    int array[] = {12,9,4,99,120,1,3,10,13};

    System.out.println("       Quick Sort\n\n");
    System.out.println("Values Before the sort:\n");
    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("\nValues after the sort:\n\n");
    for(i = 0; i
      System.out.print(array[i]+"  ");
   

  }

  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) / 2];
    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);
  }
}