Quicksort implementation in Java

Question

I have tried to implement Quicksort and it's not working properly.

Please tell me where I went wrong. Have I implemented the logic incorrectly? I tested the above code with these set of numbers - 13,26,12,15,10,15,12

public class QuickSort {

    private int array[];
    private int arrayLength;

    public void sort(int[] values) {

        if (values == null || values.length == 0)
            return;

        this.array = values;
        this.arrayLength = array.length - 1;

        quickSort(0, arrayLength);
    }

    private void quickSort(int low, int high) {
        int i = low, j = high;

            // Maximum Number of elements should be equal to arraylength
            int leftSubArray[] = new int[high+1];
            int rightSubArray[] = new int[high+1];

            int pivot = array[low];
            System.out.println("Pivot = " + pivot + " and position = " + low);

            int tempMax = low;

            // Divide the list in two parts

            // Left sublist smaller than pivot
            // Incremented by one to exclude the pivot
            while (i < high) {
                if (array[i + 1] < pivot) {
                    leftSubArray[tempMax] = array[i + 1];
                    tempMax++;
                }
                i++;
            }

            // Right sublist greater than pivot
            tempMax = j;
            while (j > low) {
                if (array[j] >= pivot) {
                    rightSubArray[tempMax] = array[j];
                    tempMax--;
                }
                j--;
            }

            // Combining both the arrays
            i = low;
            while (i <= tempMax) {
                array[i] = leftSubArray[i];
                i++;
            }

            array[tempMax] = pivot;

            // defining the limit of the next recursive call
            j = tempMax-1;
            i = low;

            tempMax++;
            while (tempMax <= high) {
                array[tempMax] = rightSubArray[tempMax];
                tempMax++;
            }

            displayArray();

            // Recursion
            if (low < j) 
                quickSort(low, j);

            tempMax++;
            if (tempMax < arrayLength)
                quickSort(tempMax, arrayLength);

    }

    private void displayArray() {
        for (int i : array) {
            System.out.print(i + ",");
        }
        System.out.println("\b\n");
    }
}

EDIT: Here is the console o/p from Eclipse:

Pivot = 13 and position = 0
12,10,12,13,26,15,15,

Pivot = 12 and position = 0
10,12,12,13,26,15,15,

Pivot = 26 and position = 4
10,12,12,13,15,15,26,

Pivot = 15 and position = 4
10,12,12,13,15,15,26,

Pivot = 15 and position = 4
10,12,12,13,15,15,0,

Pivot = 10 and position = 0
10,0,0,13,15,15,0,

Pivot = 15 and position = 4
10,0,0,13,0,15,15,

Pivot = 0 and position = 4
10,0,0,13,0,0,0,

Pivot = 10 and position = 0
0,0,10,0,0,0,0,

Pivot = 0 and position = 0
0,0,10,0,0,0,0,

Pivot = 0 and position = 3
0,0,10,0,0,0,0,

Pivot = 0 and position = 0
0,0,0,0,0,0,0,

"It's not working properly" is not an adequate description of any problem. Does it crash? Produce incorrect results? What exactly is wrong? — Henry Keiter
– Henry Keiter, Commented Apr 9, 2014 at 14:47
Woah that's quite a lot of code for quicksort, and very unusual (no partition function?). And why don't you do it in place? That's the main advantage of it. You might be introducing a lot of bugs just because of how you are implementing it. — Giovanni Botta
– Giovanni Botta, Commented Apr 9, 2014 at 14:50
It's very odd that you have that outer loop there. The basic quick sort algorithm goes: partition, recurse, recurse. I'd suggest you get that working before making things more complicated. — Theodore Norvell
– Theodore Norvell, Commented Apr 9, 2014 at 15:06
@abc "partitioning" refers to partitioning the array around the pivot. This is an operation typically pushed in a separate function that gets called recursively as TheodoreNorvell pointed out. You should not need to create new arrays as partition is usually implemented in place. — Giovanni Botta
– Giovanni Botta, Commented Apr 9, 2014 at 15:36

pise · Accepted Answer · 2014-04-09 14:55:28Z

1

The below is the working code.

public class QuickSort{

int arr[] = {12,9,4,99,120,1,3,130,13};


public static void main(String args[])
{

QuickSort qs = new QuickSort();

qs.quickSort(qs.arr,0,qs.arr.length-1);
System.out.println("");


}

void quickSort(int arr[],int left,int right)
{
   int i = left, j = right;

   int tmp;int p;

   int pivot = arr[(left + right) / 2];


System.out.println("");

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

}System.out.println("\n\nPivot = " +pivot+" Left= "+left+" j= " +j+ " I= "+i+ " Right= "+right+"  {before entering do-while}\n");

/* partition */

  while (i <= j) {

        while (arr[i] < pivot)

              i++;

        while (arr[j] > pivot)

              j--;

        if (i <= j) {

              tmp = arr[i];

              arr[i] = arr[j];

              arr[j] = tmp;

              i++;

              j--;

        }
/*for(p=0;p<arr.length;p++)
    {
        System.out.print(arr[p]+" ");

    }
    System.out.println();*/

  }




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

System.out.println("\n\nPivot = " +pivot+" Left= "+left+" j= " +j+ " I= "+i+ " Right= "+right+" {after each do-while}");

/***********/


 /* recursion */

  if (left < j){
    System.out.println("\nInside First if Left = "+left+ " J = " +j);       

        quickSort(arr, left, j);
}

  if (i < right){
    System.out.println("\nInside Second if i = " +i+ " Right = " +right);
        quickSort(arr, i, right);
}

/*******/

} }

answered Apr 9, 2014 at 14:55

pise

8656 gold badges26 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

abc Over a year ago

thanks for you code but I want to rectify the code which I wrote..I know its incorrect and that why is not working properly...but I have upvoted your answer

Giovanni Botta Over a year ago

@pise This question looks like a homework question. I would avoid giving working solutions in such cases, since it's better to learn by understanding and fixing your own mistakes rather than looking at a solution.

abc Over a year ago

@GiovanniBotta I would have googled and get the code directly from there but instead I tried to implement it on my own and hence posted the question.STOP judging me!

Giovanni Botta Over a year ago

@abc I apologize if I seemed judgmental, that was not my intention. Besides, I was responding to pise suggesting to help with the question rather than giving a solution. As you also noticed, you want to fix your code and understand why it's not working, which is absolutely fair and reasonable. I was just trying to make that point in general with "homework like" questions.

Community · Accepted Answer · 2017-05-23 12:21:24Z

0

With the guidance from Giovanni Botta's link and Theodore Norvell's comment I am able to implement the logic corectly.

edited May 23, 2017 at 12:21

CommunityBot

11 silver badge

answered Apr 11, 2014 at 7:56

abc

3152 gold badges5 silver badges12 bronze badges

Collectives™ on Stack Overflow

Quicksort implementation in Java

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest