Home Java Beginners Arrayexamples Quick Sort In Java
Questions:Ask|Latest


 
 

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

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

Ask Questions?    Discuss: Quick Sort In Java   View All Comments

Post your Comment


Your Name (*) :
Your Email :
Subject (*):
Your Comment (*):
  Reload Image
 
 
Comments
Euan
April 11, 2011
thank's

thank you
Jing
May 25, 2011
Bug?

Hi I think there is a problem in your implementation. Try {12,9,30,99,30,1,30,10,13}; The point is if there are more than one occurrences of the pivot and they are in symmetric positions then there is a problem. Please point out if I'm wrong. Thanks Jing
wishma prasad
June 23, 2011
computer science

i like this
Sebastian
June 24, 2011
This is incorrect

This is an incorrect implementation of Quick Sort. The algorithm fails for inputs such as this: 68 13 56 44 82 78 59 78 61 82
David
September 22, 2011
No duplicates

Hi, Fantastic short and easy to remember algorithm but it does not allow duplicate entires. For example, in your code you use the data: {12,9,4,99,120,1,3,10,13}; However, {12,9,4,99,120,1,3,10,13,13}; fails due to the extra 13. Any chance you could update the algorithm? David
joseph
October 13, 2011
quicksort

hays gays i want to learn more about more details about QUICK SORT because this my project in are school just for give me because this my for my future thank you..
Kaushalendra
January 2, 2012
Unable to run code

kindly try to run this code for { 1, 3, 6, 4, 1, 8, 3, 9, 2, 0, 1 } I am not able to run it . It goes in an infinite loop
Martin Hernandez Gonzalez
January 13, 2012
Duda

What happen if two numbers be repeated? thanks for your explication...
Vivek
January 17, 2012
Incorrect implementation

The implementation is incorrect. It fails for input 1,2,3,4,8,9,76,54,58,50,322,11,44,11
riz
January 24, 2012
changing the output of the quick sort.

please help me in getting the output in this fashion. using array the below example is using link list though. but i need it in arrays. please modify the above program so that i can get the following output. Initial List: 5 -> 9 -> 2 -> 9 -> 7 -> null Level 0: Before Left: 2 -> null Level 0: Before Pivot is: 5 Level 0: Before Right: 9 -> 9 -> 7 -> null Level 1: Before Left: 7 -> null Level 1: Before Pivot is: 9 Level 1: Before Right: 9 -> null Level 1: After Left: 7 -> null Level 1: After Pivot is: 9 Level 1: After Right: 9 -> null Level 0: After Left: 2 -> null Level 0: After Pivot is: 5 Level 0: After Right: 7 -> 9 -> 9 -> null Sorted List: 2 -> 5 -> 7 -> 9 -> 9 -> null
m.nadipi naganna
March 15, 2012
algorithms and datastructures

u r services is very excellent.
C:
May 7, 2012
code

helped alot thanks
Nguyen Chi Vien
June 2, 2012
more than 2 numbers are equal!!

please test with: array[] = {12,99,4,99,120,1,3,10,13}; loop loop and loop... need to change: while (lo<hi && array[hi] > mid) { ----> while (lo<hi && array[hi] >= mid) {
Raj
June 8, 2012
algo review..

I think this description of quick sort is very complicated. The algo is simple. take pivot, put all smaller items in left and bigger items in right. repeat same thru recursion...
varun
June 30, 2012
try this code for....{11,12,12,1}

try this code for....{11,12,12,1}..there is some issue....loop is not breaking....
Matt
July 1, 2012
This is a bad implementation of quick sort!

Use {0,0,0} as the input and it will loop forever! Shame on you.
Amit
July 10, 2012
solution doesnt work

Hangs for the input 9 7 7 2 2 3
korea
July 30, 2012
where is 9 on the result?

title
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