I am trying to implement QuickSort in java but Could not get output?

Question

I am trying to implement a quickSort by taking last Element as the pivot. But I am unable to produce a valid output.

Also what change needs to be done in order to make it randomized? I am coding in Java.

public class QuickSortDemo {
    public static void quicksort(int A[], int temp[], int left, int right) {
        int q, i;

        //why u need to check this  base case always
        if (left < right) {
            q = partition(A, temp, left, right);
            quicksort(A, temp, left, q - 1);
            quicksort(A, temp, q + 1, right);

            for (i = 0; i < A.length; i++) {
                System.out.println(A[i]);
            }
        }
    }

    public static int partition(int A[], int temp[], int left, int right) {
        int x, i, j;

        x = A[right];
        i = left - 1;

        for (j = left; j <= right - 1; j++) {
            if (A[j] <= x) {
                i = i + 1;
                A[i] = A[j];
            }
        }

        A[i + 1] = A[right];
        return i + 1;
    }

    public static void main(String s[]) {
        int ar[] = {6, 3, 2, 5, 4};
        int p[] = new int[ar.length];
        quicksort(ar, p, 0, ar.length - 1);
    }
} //end class QuickSortDemo

OutputShown

Why does `i` start at `left-1`? If `left` is zero, this causes an `ArrayIndexOutOfBoundsException`! — lodo, Mar 28 '15 at 10:45
@lodo I have shown u output but i don't have clue what the output is coming — mansi kbchawla, Mar 28 '15 at 11:01
You're *overwriting* values, not *swapping* them in your `partition` method. — fabian, Mar 28 '15 at 11:24
Can you please explain the reason of implementing it in this way ?? there are easier and better recursive example available. I thing you should take a look into them too first. — Om., Mar 28 '15 at 11:32

bbastu · Accepted Answer · 2015-03-30T12:55:35.090

As mentioned in the comments, there are some errors in the partition method. When implementing quicksort you want to swap the elements in the array and not just overwrite the ones in the front. They would be lost.

Furthermore, the code starts on the left and always swappes every element that is less or equal to the pivot. These are unnecessary operations if the element is already in the correct part of the array.

It is better to search for an element that is greater than the pivot from the left. Then, search for an element that is less than the pivot from the right, to only swap those and then continue until all necessary elements have been swapped.

The standard implementation (that I know) would look something like this

public static int partition(int A[], int left, int right) {
    int pivot, i, j;

    pivot = A[right];
    i = left;
    j = right - 1;

    do {
        // Search for element greater than pivot from left, remember position
        while ( A[i] <= pivot && i < right ) i++;

        // Search for element less than pivot from right, remember positon
        while ( A[j] >= pivot && j > left ) j--;

        // If elements are in the wrong part of the array => swap
        if ( i < j ) swap( A, i, j );

    // Continue until the whole (sub)array has been checked    
    } while ( j > i );

    // Put the pivot element at its final position if possible
    if ( A[i] > pivot )
        swap ( A, i, right );

    // Return the border / position of the pivot element    
    return i;
}

The swap is as usual

public static void swap(int[] A, int first, int second) {
    int temp = A[first];
    A[first] = A[second];
    A[second] = temp;
}

Also note, that there is no need to use temp within this code. Your code declares it in its signatures but never uses it.

No its taking a pivot element either taking the leftmost element or rightmost or somewhere in the middle — mansi kbchawla, Mar 28 '15 at 14:22

score 1 · Answer 2 · answered Mar 28 '15 at 12:23

Here a code that I came up with. Here I take the right most value as the pivote value and the carry onward. Through recursive carried on further. Hope you got an understanding.

 public class QuickSortDemo {
    public static void main(String[] args) {
    int[] input = {6, 3, 2, 5, 4};
    int[] output = quickSort(input, 0, input.length-1);
    for(int a : output) {
    System.out.println(a);
    }}
    public static int[] quickSort(int[] array, int lowerIndex, int higherIndex) {

     int i = lowerIndex;
     int j = higherIndex;
     // calculate pivot number, rightmost value
     int pivot = array[higherIndex];
     // Divide into two arrays
     while (i <= j) {
     while (array[i] < pivot) {
     i++;
     }
     while (array[j] > pivot) {
     j--;
     }
     if (i <= j) {
     int temp = array[i];
     array[i] = array[j];
     array[j] = temp;
     //move index to next position on both sides
     i++;
     j--;
     }
     }
     // call quickSort() method recursively
     if (lowerIndex < j)
     quickSort(array,lowerIndex, j);
     if (i < higherIndex)
     quickSort(array, i, higherIndex);

     return array;
     }
    }

Yes i understood What changes do we make by taking random() element to shorten worst case complexity? — mansi kbchawla, Mar 28 '15 at 13:18
Yes. Indeed. You can use a random Value as a best practice. For more understanding refer this Question. [http://stackoverflow.com/questions/164163/quicksort-choosing-the-pivot] — Anjula Ranasinghe, Mar 28 '15 at 13:27

I am trying to implement QuickSort in java but Could not get output?

2 Answers2