Quicksort not sorting

java, quicksort

Solution

This is what you want to do:

private static void swap(double[] a, int i, int j) {
    double t = a[i];
    a[i] = a[j];
    a[j] = t;
}

private static int partition(double [] a, int left,int right,int pivotIndex)
{
    swap(a, pivotIndex, right);
    int pos = left;//represents boundary between small and large elements
    for(int i = left; i < right; i++)
    {
        if (a[i] < a[right])
        {
            swap(a, i, pos);
            pos++;
        }
    }
    swap(a, right, pos);
    return pos;
}

I made the code clearer by having a helper `swap` method. You had 3 bugs in the original code:

- The one-off error on the loop boundary

- You're using the wrong index to get the pivot element in the loop

- You swapped elements at the wrong indices after the loop

Problem

So I am trying to create a quicksort method, however, it is not sorting properly. Heres my input and output Original array: 80.0 10.0 50.0 70.0 60.0 90.0 20.0 30.0 40.0 0.0 Sorted array: 0.0 30.0 20.0 80.0 40.0 60.0 70.0 10.0 90.0 50.0 I tried changing the for loop to `for(int i = left; i < right; i++)` but now the output is: 0.0 20.0 30.0 40.0 80.0 10.0 60.0 90.0 70.0 50.0 ``` public static void sort(double[] a) { quickSort(a, 0, a.length-1); } public static void quickSort(double [] a, int left, int right) { if (left < right) { int pivotIndex = (left+right)/2; int pos = partition(a,left,right,pivotIndex); quickSort(a,left,pos-1); quickSort(a,pos+1,right); } } private static int partition(double [] a, int left,int right,int pivotIndex) { double temp = a[pivotIndex]; a[pivotIndex] = a[right]; a[right] = temp; int pos = left;//represents boundary between small and large elements for(int i = left; i < right-1; i++) { if (a[i] <= a[pivotIndex]) { double temp2 = a[i]; a[i] = a[pos]; a[pos] = temp2; pos++; } } double temp3 = a[pivotIndex]; a[pivotIndex] = a[pos]; a[pos] = temp3; return pos; } ```

Original source