We have to make an optimized quicksort for out own Comparable base class. For the life of me I cannot make it work. The algorithm seems straight forward, however I cannot seen to get my code to work. I have a DateTime class that extends Comparable that I am using to test and the sort seems to work but one out of every 20 or so runs a single value is out of place and when I use insertion sort on chunks of the array that are less than 8 the whole sort gets thrown out of whack.
In my partition method it kind of works when I move the pivot to the end and start my pointers at the start and end - 1. I want to move the pivot to end - 1 because the first and last are already sorted and start the pointers at first + 1 and end -2 but everything falls apart if I try that and I don't understand why.
So I have something that works now. It gets a little spastic when I don't use insertion sort on smaller sub arrays which bothers be but ill figure it out eventually. Thanks to ben j for pointing out about falling out of the array...that was causing the insertion sort issue. :)
My current code is below
Comparable** partition(Comparable** from, Comparable** to)
{
Comparable** pivot = from + (to - from) / 2;
SortFirstMiddleLast(from, pivot, to - 1);
swap(*pivot, *to);
pivot = to;
++from; to -= 2;
while (from <= to)
{
while (**from <= **pivot && from <= to) ++from;
while (**to >= **pivot && from <= to) --to;
if (from < to)
{
swap(*from, *to);
++from; --to;
}
}
swap(*from, *pivot);
return from;
}
The key process in quickSort is a partition(). The target of partitions is, given an array and an element x of an array as the pivot, put x at its correct position in a sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x.
Quick sort is an in-place sorting algorithm. In-place sorting means no additional storage space is needed to perform sorting. Merge sort requires a temporary array to merge the sorted arrays and hence it is not in-place giving Quick sort the advantage of space.
In practice, Quick Sort is usually the fastest sorting algorithm. Its performance is measured most of the time in O(N × log N). This means that the algorithm makes N × log N comparisons to sort N elements.
From the code you've shown us and your comment about what goes wrong my only guess is that from
and to
do not mean what you think. Your code has to - from
as the length of the segment to sort. If that's exact (and not just approximate for pivot selection) that would mean that to
was actually pointing at an element just beyond the region to sort. That's reasonable, but then swap<Comparable*>(*pivot, *(to))
would be swapping the pivot off the end of the list.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With