Re: Quicksort done. Can I get a check on it?

On 6/30/2013 1:15 PM, Christopher Pisz wrote:


I think I've implemented a Quicksort after much Googling. I based it
upon someone elses and walked through it on paper a few times. I am
not too certain this meets the criteria. In debugging it, it seems to
sort the given collection upon the first frame of recursion, yet it
keeps calling itself anyway. When it does call itself again, it just
goes through the checks and calls itself again, and goes through the
checks... So I had a stack 5 deep or an equal number of calls as there
were elements. Perhaps I am confused. Should there not be a way to
determing, "Hey we are sorted!, all done!" I cannot claim to follow it
completely. It is one of those fuzzy implementations that is sinking
in.

Here is what I have:

//---------------------------------------------------------------------
---------- #include <algorithm>
#include <iostream>
#include <vector>

//---------------------------------------------------------------------
---------- /// Quick Sort
/// Choose a pivot point and remove it from the collection
/// For each element in the collection, if it is less than the pivot
than add it to another collection 'less', otherwise add it to another
collection 'greater'
/// Perform quicksort recursively on 'less' and 'greater' and
concatentate the results as 'less' 'pivot' 'greater'
/// Best Case Complexity O(nlogn)
/// Average Complexity O(nlogn)
/// Worst Case Complexity O(n^2)

size_t QuickSortPartition(unsigned int * collection, size_t
beginIndex, size_t endIndex)
{
     unsigned int pivotValue = collection[beginIndex];
     size_t pivotIndex = beginIndex;

     while( pivotIndex < endIndex )
     {
         while( pivotValue < collection[endIndex] &&
                endIndex > pivotIndex )
         {
             --endIndex;
         }

         std::swap(collection[pivotIndex], collection[endIndex]);

         while( pivotValue >= collection[pivotIndex] &&
                pivotIndex < endIndex )
         {
             ++pivotIndex;
         }

         std::swap(collection[endIndex], collection[pivotIndex]);
     }

     return pivotIndex;
}

void QuickSort(unsigned int * collection, size_t beginIndex, size_t
endIndex)
{
     // Nothing to do when container is empty or only has one element
     if( beginIndex >= endIndex )
     {
         return;
     }

     size_t pivotIndex = QuickSortPartition(collection, beginIndex,
endIndex);

     if( pivotIndex > beginIndex)
     {
         QuickSort(collection, beginIndex, pivotIndex - 1);
     }

     if( pivotIndex < endIndex )
     {
         QuickSort(collection, pivotIndex + 1, endIndex);
     }
}

//---------------------------------------------------------------------
--------- void Display(unsigned int * begin, size_t size)
{
     for(size_t index = 0; index < size; ++index, ++begin)
     {
         std::cout << ' ' << *begin;
     }
     std::cout << '\n';
}

//---------------------------------------------------------------------
--------- /// Test driver
int main()
{
     unsigned int collection[] = {5,2,4,1,3};

     // Quick sort
     QuickSort(collection, 0, sizeof(collection) / sizeof(unsigned
     int)
- 1);
     Display(collection, sizeof(collection) / sizeof(unsigned int));

     system("pause");
     return 0;
}