Quick Sort in java is not correct

Question

I have been trying to understand what is happening here:

import java.util.Random;

public class QuickSort {
    static Random random = new Random();

    static void quickSort(int[] arr,
                          int lo,
                          int hi){
        //best case
        if(lo >= hi){return;}

        int pivot = partition(arr,lo,hi);

        quickSort(arr, pivot+1, hi);
        quickSort(arr, lo, pivot-1);
    }

    static int partition(int arr[],
                         int lo,
                         int hi){
        int pivPoz=lo + random.nextInt(hi - lo + 1);
        int pivot = arr[pivPoz];

        int index = lo - 1;

        for(int i = lo;i<=hi; i++){
            if(arr[i] <= pivot && i!=pivPoz ){
                index++;
                int a = arr[index];
                arr[index] = arr[i];
                arr[i] = a;
            }
        }

        index++;
        int a = arr[index];
        arr[index] = arr[pivPoz];
        arr[pivPoz] = a;

        return index;
    }

    public static void main(String[] args){

        int arr[] = new int[]{4,2,8,12,30,1,3,9,10,9,12};
        quickSort(arr,0,arr.length-1);
        for(int i : arr){
            System.out.print(i + "\t");
        }
    }
}

This is my Quick Sort algorithm in Java. I know the code is too lengthy, and I can do it better, but I can do it after I solve this error. I remarked something strange. I am running the same program with the same input but ends with different outcomes, for instance:

1. input = {4,2,8,12,30,1,3,9,10,9,12} output = {1 2 3 4 8 9 9 10 12 12 30}

2. input = {4,2,8,12,30,1,3,9,10,9,12} output = {8 3 2 4 9 9 10 12 12 30 1}

3. input = {4,2,8,12,30,1,3,9,10,9,12} output = {2 4 8 9 9 10 12 3 1 12 30}

I have changed nothing in the code just run it. Do you have any suggestion why this could have happened?

Answer 1

The problem is that in your Lomuto-like algorithm, you leave the pivot within the range that is being iterated. You do have some precaution with i != pivPoz, but that still leaves some room for problems when index overtakes pivPoz:

When index++ makes index equal to pivPoz, the pivot is swapped to another index, and so you will lose track of where the pivot is, and return the wrong index.

The usual way to avoid these problems is to first swap the randomly selected pivot to the right end of the range, so it is at index hi. This index is then excluded from the loop, and you'll not have this problem occurring.

Here is your partition code with that correction (I also moved the swap-logic in a separate function):

    static void swap(int arr[], int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    static int partition(int arr[], int lo, int hi) {
        swap(arr, lo + random.nextInt(hi - lo + 1), hi);
        int pivot = arr[hi];
        int index = lo - 1;
        for(int i = lo; i < hi; i++) {
            if (arr[i] <= pivot) swap(arr, ++index, i);
        }
        swap(arr, ++index, hi);
        return index;
    }