Java QuickSort algorithm

Question

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.

Have you tried adding a println at the beginning of QuickSort to print the subarray between left and right, so you can find out exactly when something unexpected happens? — Stef
– Stef, Commented Sep 9, 2020 at 12:05
@Stef Nobody said something else. It is still important to make people aware of flaws in their communication. One part of becoming a programmer ... is to accept: all details matter. — GhostCat
– GhostCat, Commented Sep 9, 2020 at 12:08
I've realized my mistake and I've edited the post. Yes the program compiles without any errors and I've found it only sorts the left part of the array and not the right part, If this helps you to understand the issue. — Simeon Stoyanov
– Simeon Stoyanov, Commented Sep 9, 2020 at 12:15

IQbrod · Accepted Answer · 2020-09-09 12:50:21Z

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

Collectives™ on Stack Overflow

Java QuickSort algorithm

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related