Java Quicksort how to swap middle element with pivot

Question

I am trying to implement the quicksort algorithm using Java. I have created my partition function as follows:

int [] quickPartition(int[] array, int low, int high){

    int  pivot = array[low], end_mark = high, start_mark = 1, temp;

    while (start_mark != end_mark) {
        if (array[start_mark] > pivot) {
            while (end_mark != start_mark) {
                if (array[end_mark] < pivot) {
                    temp = array[end_mark];
                    array[end_mark] = array[start_mark];
                    array[start_mark] = temp;

                    break;
                }
                end_mark--;
            }
        }
        start_mark++;
    }

    return array;
}

array[low] is my pivot, end_mark is the last element of the array and start_mark is the first element after pivot

The first while loop loops from the start towards the end looking for the next number larger than the pivot. When found, the second loop starts from the end of the array towards the start looking for the next number smaller than the pivot. If both of these conditions are satisfied, swapping occurs. However, if the both the looping indices(startindex and endindex) meet, the while loops exit.

Sample array: [54, 26, 93, 17, 77, 90, 31, 44, 55, 20]
Returned: [54, 26, 20, 17, 44, 31, 90, 77, 55, 93]

As you can see, the relevant elements have been partitioned. However, the last step involves swapping the pivot(54) and (31), So that all elements greater than 54 are on the right and those less than 54 are on the left. How do you swap 31 and 54 yet at this point(where start_index == end_index) the while loop has already stopped? Take note that if you swap outside the while loops the value 31 will be lost.

Your code seems logically wrong. Note that merge sort requires that at least one element should be in its proper place after each iteration. Your code will never swap 55 since it is always greater than 54 which is the pivot. You need to change your pivot after each iteration! — Tejash Desai
van Emden improved on quicksort in 1970 by choosing the middle from lowest, highest and median value as the pivot instead of just lowest. Your code is nearly 50 years out of date. — stark

Brugi94 Brugi94 · Accepted Answer · 2016-10-21T13:43:54

At the end of the outer while loop, array[start_mark] will be the first number >= than the pivot, so you should swap the pivot with array[start_mark-1].

Also, this code will produce an ArrayOutOfBoundsException if the pivot is the minimum value in the array: end_mark would decrease until end_mark == start_mark == 1. Then start_mark would become 2, and the outer while loop condition won't be met. Setting the condition of the outer while loop to start_mark<=end_mark should fix this. The code would look like this

int  pivot = array[low], end_mark = high, start_mark = 1, temp;
while (start_mark < end_mark) {
    if (array[start_mark] > pivot) {
        while (end_mark != start_mark) {
            if (array[end_mark] < pivot) {
                temp = array[end_mark];
                array[end_mark] = array[start_mark];
                array[start_mark] = temp;

                break;
            }
            end_mark--;
        }
    }
    start_mark++;
}
temp = array[start_mark-1];
array[start_mark-1] = pivot;
array[low] = temp;
return array;

Java Quicksort how to swap middle element with pivot

2 Answers