patternMinor
Proof for Unusual QuickSort Partition Scheme
Viewed 0 times
unusualpartitionschemequicksortforproof
Problem
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?
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 = j) break;
swap(a, i, j);
}
middlePivSort(a, start, j);
middlePivSort(a, j + 1, end);
}
}Solution
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
Exercise 2. Will your code still be correct if the lines
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? .Context
StackExchange Computer Science Q#106911, answer score: 3
Revisions (0)
No revisions yet.