CODEWITHSUNDEEP
javaquicksort
VCODE
VCODE

Reputation: 700

QuickSort never stops

I'm trying to implement the Quick Sort algorithm, but when I run it never stops, resulting with a StackOverflowException.

(I know that using the two stacks to rearange the array, as I do, it is not the most efficient way, but at this time this is not so important.)

 private static void quickSort(int[] a, int start, int end) {
        if (start >= end) {
            return;
        }

        int pivot = a[start];
        Stack<Integer> left = new Stack<Integer>();
        Stack<Integer> right = new Stack<Integer>();

        for (int i = start + 1; i <= end; i++) {
            if (a[i] < pivot) {
                left.push(a[i]);
            } else {
                right.push(a[i]);
            }
        }

        int arrayIndex = 0;
        int middle = 0;

        while (left.size() > 0) {
            a[arrayIndex++] = left.pop();
        }

        middle = arrayIndex;
        a[arrayIndex++] = pivot;

        while (right.size() > 0) {
            a[arrayIndex++] = right.pop();
        }

        quickSort(a, start, middle - 1);
        quickSort(a, middle + 1, end);
    }

Upvotes: 0

Views: 148

Answers (1)

laune
laune

Reputation: 31290

 int arrayIndex = 0;

must be replaced by

 int arrayIndex = start;

Upvotes: 2

Related Questions