Java QuickSort algorithm

user_5395249 0
Viewed 353

I am trying to learn Quick Sort algorithm and this is my code so far:

import java.util.Arrays;

public class JavaFiddle {
    static int[] myArray = new int[]{35, 12, 25, 1, 5, 33, 56};

    public static void QuickSort(int[] array) {
        QuickSort(array, 0, array.length - 1);
    }

    public static void QuickSort(int[] array, int left, int right) {
        if (left < right) {
            int pivot = left + ((right - left) / 2);
            int index = partition(array, left, right, pivot);
            QuickSort(array, left, index - 1);
            QuickSort(array, index + 1, right);
        }
    }

    public static int partition(int[] array, int left, int right, int pivot) {
        while (left < right) {
            while (array[left] < pivot) {
                left++;
            }
            while (array[right] > pivot) {
                right--;
            }
            if (left < right) {
                swap(array, left, right);
                left++;
                right--;
            }
        }
        return left;
    }

    public static void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(myArray));
        QuickSort(myArray);
        System.out.println(Arrays.toString(myArray));
    }
}

However, this code gives me an incorrect result:

[35, 12, 25, 1, 5, 33, 56] - before sort
[1, 12, 25, 35, 5, 33, 56] - after sort

What do I have wrong here? I cannot find the flaw in the logic.

quicksort sorting algorithm java
1 Answers

Multiple errors here,
You define pivot in main method, but quick sort algorithm will swap pivot from right element to the middle. You edit left and right values in your while loop in a while loop, which result right and left to be smaller/taller than your pivot and skipping some swaps.
Here's the correct implementation without your while { while { ... } } and a correct pivot (from right to middle)

import java.util.Arrays;
public class Main
{
    static int[] myArray = new int[] {35, 12, 25, 1, 5, 56, 33};
    public static void QuickSort(int[] array) {
        QuickSort(array, 0, array.length - 1);
    }
    public static void QuickSort(int[] array, int left, int right){
        if(left < right) {
            int index = partition(array, left, right);
            QuickSort(array, left, index - 1);
            QuickSort(array, index + 1, right);
        }
    }
    public static int partition(int[] array, int left, int right){
        int pivot = array[right];
        int first = left - 1;
        for (int j = left; j <= right - 1; j++) {
            if(array[j] < pivot) {
                first ++;
                swap(array, first, j);
            }
        }
        swap(array, first + 1, right);
        return first + 1;
    }
    public static void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
    public static void main(String[] args)
    {
        System.out.println(Arrays.toString(myArray));
        QuickSort(myArray);
        System.out.println(Arrays.toString(myArray));
    }
}

Also you compare pivot which is an index with array[...] which is a value

user_118251620
Related