Help in quicksort algorithm program in java

Question

Hi,

I'm trying to implement QuickSort algorithm program in Java, but I'm getting incorrect answer.

public class QuickSort{

    public static void main(String[] args){
        int arr[]={12,34,22,64,34,33,23,64,33};
        int i=0;
        int j=arr.length;
        while(i<j){
            i=quickSort(arr,i,i+1,j-1);

        }   
        for(i=0;i<arr.length;i++)
    System.out.print(arr[i]+" ");
    }

    public static int quickSort(int arr[],int pivot,int i,int j){


        if(i>j){

            swap(arr,pivot,j);
            return i;
        }   

        while(i<arr.length&&arr[i]<=arr[pivot]){ 

            i++;
        }   

        while(j>=1&&arr[j]>=arr[pivot]){

            j--;
        }   
        if(i<j)
            swap(arr,i,j);


        return quickSort(arr,pivot,i,j);





    }   
    public static void swap(int[] arr,int i,int j){
        int temp;
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

}

The above program giving me the output as: 12 23 22 33 34 33 64 34 64

Could anyone please tell me how can I get my desire result?

Answer 1

The problem is that this is not really how quicksort works. Quicksort is a recursive algorithm that should only be called once from outside of itself. The idea is that at each iteration, you partition the array into two halves - the left half contains all elements less than the pivot, and the right half contains all elements greater than / equal to the pivot. Then you quicksort the two halves, and finally put the pivot in the middle.

If the side that you are quicksorting is less than 3 elements long, you can just swap the two elements or leave them, and that part of the array is done.

But it doesn't look like your code is doing that at all - you are calling Quicksort 6 times from your client, and within the quicksort function you are making at most one swap. So this is not a case where someone is going to be able to look at your code and debug it by telling you to move a swap or something. You need to revisit your logic.

Check out the Wikipedia diagram for a visual example of what is supposed to happen in a single iteration:

http://en.wikipedia.org/wiki/File:Partition_example.svg

Answer 2

There are open source implementations of quicksort in Apache Harmony and Apache Mahout, probably amongst many others. You can read them.

Answer 3

Hi.. Please find comprehensive working code for quick sort algorithm implemented in Java here,

http://www.technicalypto.com/2010/01/quick-sort-in-java.html