3

Other than below, is there a better way to do quick sort using random pivot(I could not do without a swap)? Please advise 

int hoare_par (int *a, int b, int e)
{
    if (b < e) {
        int p_i = __random(b, e);
        __swap(&a[b], &a[p_i])

        int p = a[b];
        b = b - 1;
        e = e + 1;

        while (1) {
            do { ++b;} while (a[b] < p);
            do { --e;} while (a[e] > p);
            if (b < e)
                 __swap( &a[b], &a[e]);
            else
                 return e;
        }
    }
    return e;
}

Also, please let me know if incorrect. Thanks!

codey modey
  • 983
  • 2
  • 10
  • 23
  • 1
    Don't want to be rude but if you don't do your research on quick sort and not tested your code for correctness why should we care? – Logman Jul 04 '16 at 00:24
  • I tested at my end, did my research too. But yes, above implementation might not be as correct as yours and mine research might not be as good as yours. – codey modey Jul 04 '16 at 00:40
  • I was referring to "Also, please let me know if incorrect." but if you do your research it's ok for me. Anyway I can't think of any much better solution then yours. – Logman Jul 04 '16 at 01:20

1 Answers1

1

If you take a peek at Wikipedia's article and study the pseudocode for Hoare partitioning given there, you'll see that all the partitioning scheme cares about is that the selected pivot is somewhere in the range (it serves as a sentinel to avoid running out of the range for both indices). So you can just pick any element of the range at random as pivot element and do the partitioning as written down there.

vonbrand
  • 11,412
  • 8
  • 32
  • 52