Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Sorting for the heck of it -- Quicksort

Tags:

c++

quicksort

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;
}
like image 521
Falko Avatar asked Apr 24 '11 19:04

Falko


People also ask

How sorting is done in Quicksort?

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.

Why Quicksort is considered as best sorting?

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.

Is Quicksort really the fastest sorting algorithm how and why?

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.


1 Answers

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.

like image 53
Ben Jackson Avatar answered Sep 27 '22 18:09

Ben Jackson