3
$\begingroup$

TL:DR I wrote code for a QuickSort variant. It seems a bit off from original QuickSort. Can anyone tell me why and how this works? Is it a quicksort?


The following is code I wrote for a middle pivot quicksort for a high school class of AP CS.

It works for some reason. I've also found a few versions that are same or similar to this. But I'm not sure if this is the same thing as the Hoare implementation scheme. I've tried to analyze it but found out it was quite different from the quicksort I knew of -> which takes form of: elements smaller than piv | piv ~ piv | elements greater than piv. But this one acts like elements not greater than piv | elements not less than piv. Elements that are equal to the pivot can end up anywhere in between. But it works. Is this even quicksort?

public static void middlePivSort(int[] a, int start, int end) {
    if(start < end) {
        int i = start - 1;
        int j = end + 1;
        int m = start + (end - start) / 2;
        int v = a[m];

        while(true) {
            while (a[++i] < v);
            while (v < a[--j]);

            if (i >= j) break;

            swap(a, i, j);
        }

        middlePivSort(a, start, j);
        middlePivSort(a, j + 1, end);
    }
}
$\endgroup$
3
$\begingroup$

Welcome to the fascinating world of sorting algorithms!

Apparently, you get the terminologies the other way around.

What you have implemented is none other than the classic/standard/conventional version of quicksort by Hoare partition scheme.

The version of quicksort that you knew of, "which takes form of: elements smaller than piv | piv ~ piv | elements greater than piv", is probably a variation of quicksort using a variation of Lomuto partition scheme that is good at sorting arrays with many repeated elements.

Exercise 1. Will your code still be correct if the line int m = start + (end - start) / 2; is changed to int m = start;?

Exercise 2. Will your code still be correct if the lines int m = start + (end - start) / 2; int v = a[m]; is changed to int v = (a[start] + a[end]) / 2? .

$\endgroup$
  • $\begingroup$ thank you! i was very confused with the terminologies as i only learned lomuto's version in class and thought that the pivot should always be at the returned index; even in hoare's version. the answers to the exercises would be both true? hoare's version seems to work regardless of the location of pivot (i've tried random pivot sorting, and it works fine). $\endgroup$ – user102891 Apr 14 at 4:08
  • $\begingroup$ I'm kinda confused about (2). it seems to work when I test the code. So, does hoare work even with "any" pivot values? (as a[start] + a[end] / 2 might not be a value within the array). but when i place a fixed value such as 100 as the pivot, it doesn't work... $\endgroup$ – user102891 Apr 14 at 4:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy