Home Java Beginners Arrayexamples Quick Sort In Java

Related Tutorials


 
 

Share on Google+Share on Google+

Quick Sort In Java

Advertisement
In this example we are going to sort integer values of an array using quick sort.

Quick Sort in Java

     

Introduction

In this example we are going to sort integer values of an array using quick sort.

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).

Code description:

In quick sort algorithm pick an element from array of elements. This element is called the pivot. Then compare the the values from left to right until a greater element is find then swap the values. Again start comparison from right with pivot. When lesser element is find then swap the values. Follow the same steps until  all elements which are less than the pivot come before the pivot and all elements greater than the pivot come after it. After this partitioning, the pivot is in its last position. This is called the partition operation. Recursively sort the sub-array of lesser elements and the sub-array of greater elements.

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("\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.printarray[i]+"  ");
  System.out.println();
  quick_srt(array,0,array.length-1);
  System.out.print("Values after the sort:\n");
  for(i = 0; i <array.length; i++)
  System.out.print(array[i]+"  ");
  System.out.println();
  System.out.println("PAUSE");
  }

  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 + hi2];
  while (lo < hi) {
  while (lo<hi && array[lo< mid) {
  lo++;
  }
  while (lo<hi && array[hi> 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+: lo, n);
  }
}

Output of the example:

C:\array\sorting>javac QuickSort.java
C:\array\sorting>java QuickSort
       RoseIndia
       Quick Sort
Values Before the sort:
12  9  4  99  120  1  3  10  13
Values after the sort:
1  3  4  9  10  12  13  99  120
PAUSE
C:\array\sorting>_

Download this example.

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 28, 2007

Related Tutorials

Discuss: Quick Sort In Java   View All Comments

Post your Comment


Your Name (*) :
Your Email :
Subject (*):
Your Comment (*):
  Reload Image
 
 
Comments:27
Arumugam
August 8, 2012
There is some problem in the above code

try this Array int array[] = { 1,2, 8, 2, 6, 0, 11, 13, 3, 4 };
Afsar Ali
August 31, 2012
this code fails for duplicate values

this code fails for duplicate values
Ivan Garcia
October 9, 2012
Exception

I was using your method, but I found an exception, the programm hangs out when we have for example an array: 12,9,4,99,12,1,3,10,13 where there are two number 12. I'd would like to know why it's happening when we execute that? Thanks in advantage. Kind Regards.
Raul
November 11, 2012
Not working fine

Try this array : int array[] = {-12, 9, 4, 99, 120, -1, 3, 10, -1}; int array[] = {-12, 9, 4, 99, 120, -1, 3, 10, -12}; recursion does not finish with negative numbers in some cases and even with positive numbers like this : int array[] = {120, 9, 4, 99, 120, 1, 3, 10, 120}; //does not finish Fix it.
ANdres Luque
March 26, 2013
Not as explained

Hello, if you print each step of the quicksort method you will see that the steps of finding the high value and swaping are wrong
Mario
April 14, 2013
Explanation

Please can you explain me: quick_srt(array, low, lo); quick_srt(array, lo == low ? lo+1 : lo, n); Thanks in advance.
waheduzzaman
June 16, 2013
for those who faces problem with duplicate entries

just place an 'if' condition to check whether it has the same value or not. If there is a match just let it where it is..otherwise let it execute other condition.. The code should be like: public static void quick_sort(......){ ................. ........... .................... ............. if(array[hi]==array[lo]){ //here do nothing } if (lo < hi) { int T = array[lo]; array[lo] = array[hi]; array[hi] = T; } if (lo < hi) { int T = array[lo]; array[lo] = array[hi]; array[hi] = T; } } hope this will help... thanks
adil madih
August 1, 2013
a suggestiom

Hi, i really love this site, but noticing some of your ads deviating from serving your mission, which is contributing to research and accademia, makes me really wondering. i strongly suggest that you get ride of that offensive dating ad. those pictures dont inspire of dating, but of prostitution. come on guys looke at them. Regards, Adil
iano90
November 18, 2013
Bug Fixed

along with the help of a tutor in college we managed to solve the problem where reoccurring values would cause an infinite loop. This was due to a missing counters within the if statement at the end of a while loop. This was causing the loop while loop to freeze. The correct code should be: while (lo < hi) { while (lo<hi && array[lo] < mid) { lo++; } while (lo<hi && array[hi] > mid) { hi--; } if (lo < hi) { int T = array[lo]; array[lo] = array[hi]; array[hi] = T; lo++; hi--; } }
DMCA.com