0

Here's the code:

public class QuickSort {

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

    private static void sort(int[] a, int lo, int hi) {
        if(hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
    }

    private static int partition(int[] a, int lo, int hi) {
        int v = a[0];
        int i = lo, j = hi+1;
        while(true) {
            while(a[++i] < v) {
                if(i == hi) {
                    break;
                }
            }
            while(a[--j] > v) {
                if(j == lo) {
                    break;
                }
            }
            if(i >= j) {
                break;
            } else {
                exch(a, i, j);
            }
        }
        exch(a, lo, j);    // <- exchange the value of a[lo] and a[j]
        return j;
    }
}

What's wrong with my code? I know it's a really simple algorithm but just cannot figure out where the problem is.

Please help me, thx in advance.

1

1 Answer 1

5

I guess the partition function of yours has a bug. The vertex (pivot) v that you are selecting should be set to a[lo] and not a[0] everytime.

And, then set i = lo + 1 and j = hi

4
  • When v equals a[lo], then, i = lo would do one redundant iteration. It will give the correct result though.
    – vish4071
    Dec 1, 2015 at 7:20
  • Sorting an already sorted array will be worst case using v=a[lo]. Use v = a[(lo + hi)/2], and then the checks for i==hi and j==lo are no longer needed.
    – rcgldr
    Dec 1, 2015 at 9:11
  • @rcgldr, I can always produce a worst case if you are choosing a "fixed" (formula for) pivot, like a[lo] or a[(lo+hi)/2] etc. If you truly want to avoid it, choose a random pivot, like v = a[rand], where rand = random number in range (lo,hi)
    – vish4071
    Dec 1, 2015 at 9:34
  • Yes there's always a worst case unless you resort to median of medians with n/5 factor (or n/7, n/9, ...), but then it's slow. A fixed centor pivot will still have worst cases, but at least sorted or reverse sorted arrays are handled. Also quicksort with Hoare partition scheme doesn't need those i==hi and j==lo checks.
    – rcgldr
    Dec 1, 2015 at 12:15

Not the answer you're looking for? Browse other questions tagged or ask your own question.