Quick Sort in Java

Question

I recently started learning about algorithms and data structure's. I decided that for every algorithm I learn about I'll implement it without looking at any pseudo code or actual code.

I have implemented Quick Sort using Hoare's Partition. The pivot is the last element in the array. Can someone check and tell me if its correctly implemented. It works correctly in all cases.

   public class JavaApplication1 {


    public static void main(String[] args) {
        int arr[] = {10,9,8,7,6,5,4,3,2,1};
        quickSort(arr, 0, arr.length - 1);

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


    public static void quickSort(int[] items, int startIndex, int endIndex) {
        if (endIndex - startIndex < 1) {
            return;
        }
        int pivotIndex = partition(items, startIndex, endIndex);
        quickSort(items, startIndex, pivotIndex - 1);
        quickSort(items, pivotIndex + 1, endIndex);
    }

    public static int partition(int[] items, int startIndex, int endIndex) {
        int left = startIndex;
        int right = endIndex - 1;
        int pivot = items[endIndex];

        while (left < right) {
            while (left <= right && items[left] < pivot) {
                ++left;
            }
            while (left <= right && items[right] > pivot) {
                --right;
            }
            if (left < right) {
                int temp_item = items[left];
                items[left] = items[right];
                items[right] = temp_item;
            }
        }

        //swap pivot to the new position
        if (items[left] > pivot) {
            int temp_item = items[left];
            items[left] = pivot;
            items[endIndex] = temp_item;
        }
        return left;
    }

}

Its a bit different than some of the code I saw online after I finished implementing it.

Answer 1

This code is not working properly if the input array contains duplicates, and it will cause an infinite loop.

You can see it by the fact that your inner while loops do not cover equality case, left won't be increased and right won't be decreased for duplicate elements.

I believe this is a bug and not intended behavior, but if it is - consider throwing an exception when you encounter an element which equals the pivot.

Another issue is with the pivot selection. When last element is a pivot, it is easy to generate a malicious input that will cause your code to run in quadric time. An easy solution to this problem is choosing a random element and making it the pivot.

Answer 2

This program had 2 problems pertaining to the partition method.

Thanks to @amit who helped me out for problem #1.

---

Problem :

1. The program would go into a infinite loop if the input array had 2 or more duplicates of an element.

The 2 inner while loops in the partition method (shown below) would stop executing as soon as an index having same value as pivot was pointed at.

while (left <= right && items[left] < pivot)

while (left <= right && items[right] > pivot)

Solution :

The intended action should have been to keep executing the loops until the variable left & right pointed at the value larger & smaller than pivot respectively.

while (left <= right && items[left] <= pivot)

while (left <= right && items[right] >= pivot)

---

Problem :

2. The program would unsort a sorted array. Eg : {1,2,3} became {2,1,3}

The outer most while loop i.e while(left < right) would never execute in the case when array size was 2. because both left and right were pointing at same index.

It would then proceed to swap the pivot present in the last location with element in the 1st location.

Eg: {1,2} became {2,1}

Solution :

changing the outer while loop to while (left <= right) fixed the problem as it now accepts an input array of size 2 or more.

---

Finally,

Removed the following if statement that placed the pivot in its new location:

  if (items[left] > pivot) {
            int temp_item = items[left];
            items[left] = pivot;
            items[endIndex] = temp_item;
        }

The if statement was a temporary fix for problem #2.

---

Updated Partition Method:

public static int partition(int[] items, int startIndex, int endIndex) {
        int left = startIndex;
        int right = endIndex - 1;
        int pivot = items[endIndex];

        while (left <= right) {
            while (left <= right && items[left] <= pivot) {
                ++left;
            }
            while (left <= right && items[right] >= pivot) {
                --right;
            }
            if (left < right) {
                int temp_item = items[left];
                items[left] = items[right];
                items[right] = temp_item;
            }
        }

        //swap pivot to the new position

            int temp_item = items[left];
            items[left] = pivot;
            items[endIndex] = temp_item;

        return left;
    }