Quicksort done. Can I get a check on it?

Newsgroup: comp.lang.c++

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

From: Christopher Pisz <cpisz@...>

Date: Sun, 30 Jun 2013 18:39:23 -0500



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

> So, I'll try a few using plain old array and come back if I get stuck.



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;

}

via Usenet Forums - Usenet Search,Free Usenet - comp.lang.c++ http://www.pocketbinaries.com/usenet-forums/showthread.php?32342-Quicksort-done-Can-I-get-a-check-on-it&goto=newpost

View all the progranning help forums at:

http://www.pocketbinaries.com/usenet-forums/forumdisplay.php?128-Coding-forums