JAVA QUICKSORT...why is this not working

Question

Why is this code not working ? The following is a recursive approach to quicksort. Can somebody also suggest a better partitioning algorithm with pivot take as first element ?

import java.util.*;
class QuickSort
{


public static void callQuickSort(int[] array,int left,int right)
{
    if(left<right)
    {
        int s = partition(array,left,right);
        callQuickSort(array,left,s-1);
        callQuickSort(array,s+1,right);     
    }

}

public static int partition(int[] array,int left,int right)
{
    int pI = left;         //pI = partition index
    int pivot = array[right];
    for(int i=left;i<=right-1;i++)
    {
        if(array[i] <= pivot)
        {
            swap(array[i],array[pI]);
            pI++;
        }
    }

    swap(array[pI],array[right]);
    return pI;
}

static void swap(int a,int b)
{
    int temp = a;
    a = b;
    b = temp;
}


public static void main(String args[])
{
    int[] array = {7,2,1,6,8,5,3,4};//array declared
    callQuickSort(array,0,7);      
    System.out.println("Sorted array is - ");
        for(int i=0;i<8;i++)
            System.out.print(array[i]+"\t");
}

}//end of class

The output is

7   2   1   6   8   5   3   4

The above code returns the array without any change. Why isn't the array changing ?

A debugger would answer this question pretty quickly. Comes with any java-IDE. And you should probably read carefully through a description of quicksort — Paul

DontPanic DontPanic · Accepted Answer · 2017-03-14T17:45:06

In java data is passed in method by value, not by reference, so you can't use swap method as you do.

Here is working code:

class QuickSort {


    public static void callQuickSort(int[] array, int left, int right) {
        if (left < right) {
            int s = partition(array, left, right);
            callQuickSort(array, left, s - 1);
            callQuickSort(array, s + 1, right);
        }

    }

    public static int partition(int[] array, int left, int right) {
        int pI = left;         //pI = partition index
        int pivot = array[right];
        for (int i = left; i <= right - 1; i++) {
            if (array[i] <= pivot) {
                int temp = array[i];
                array[i] = array[pI];
                array[pI] = temp;
//                swap(array[i], array[pI]);
                pI++;
            }
        }

        int temp = array[pI];
        array[pI] = array[right];
        array[right] = temp;
//        swap(array[pI], array[right]);
        return pI;
    }

    /*static void swap(int a, int b) {
        int temp = a;
        a = b;
        b = temp;
    }*/


    public static void main(String args[]) {
        int[] array = {7, 2, 1, 6, 8, 5, 3, 4};//array declared
        callQuickSort(array, 0, 7);
        System.out.println("Sorted array is - ");
        for (int i = 0; i < 8; i++)
            System.out.print(array[i] + "\t");
    }

}//end of class

JAVA QUICKSORT...why is this not working

1 Answers