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;
}
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
