Home Java Beginners Arrayexamples Quick Sort in Java

Related Tutorials


 
 

Share on Google+Share on Google+

Quick Sort in Java

Advertisement
Quick sort in Java is used to sort integer values of an array. It is a comparison sort. Quick sort is one of the fastest and simplest sorting algorithm in comparison to other sorting algorithms like bubble sort, insertion sort, heap sort, etc.

Quick sort in Java is used to sort integer values of an array. It is a comparison sort. Quick sort is one of the fastest and simplest sorting algorithm in comparison to other sorting algorithms like bubble sort, insertion sort, heap sort, etc.

The complexity of quick sort in the average case is Θ(n log n) and in the worst case is Θ(n2).

In quick sort algorithm, an element called "pivot" from the array is picked randomly. Then the left and right elements of the pivot is checked. All the smaller elements to pivot are kept on the left side of pivot and bigger elements than pivot are kept on the right side of the pivot. The list is then divided in two sub-arrays, one having small numbers than pivot and the other having bigger elements than pivot. A random pivot is again selected in both of these sub-arrays and the above procedure and partitioning is followed till all the numbers are sorted and merged into a sorted array.

Example of Quick Sort in Java:

public class QuickSort{
  public static void main(String a[]){
  int i;
  int array[] = {42, 18, 23, 56, 17, 65, 34, 27};

  System.out.println("\n\n RoseIndia\n\n");
  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("Values after the sort:\n");
  for(i = 0; i = n) {
  return;
  }
  int mid = array[(lo + hi) / 2];
  while (lo < hi) {
  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);
  }
}

Output:

C:\array\sorting>javac QuickSort.java
C:\array\sorting>java QuickSort
RoseIndia
Quick Sort

Values Before the sort:
42 18 23 56 17 65 34 27

Values after the sort:
17 18 23 27 34 42 53 65

Advertisement

If you enjoyed this post then why not add us on Google+? Add us to your Circles



Liked it!  Share this Tutorial


Follow us on Twitter, or add us on Facebook or Google Plus to keep you updated with the recent trends of Java and other open source platforms.

Posted on: May 10, 2013

Related Tutorials

Discuss: Quick Sort in Java  

Post your Comment


Your Name (*) :
Your Email :
Subject (*):
Your Comment (*):
  Reload Image
 
 
Comments:0
DMCA.com