I am having trouble figuring out how to get my non recursive quicksort program to finish sorting. Here is my code

``````#include<iostream>
using namespace std;
/**
* Swaps two items
*
* @pre x and y are the items being swapped
* @post Contents of actual locations that x and y represent are swapped
* @param x given data item
* @param y Given data item
*/
void tSwap(int& x, int& y){
int temp = x;
x = y;
y = temp;
}//end swap
/**
* Chooses a pivot for quicksorts parition algorithm and swaps it with
* the first item in the array
*/
void choosePivot(int theArray[], int first, int last){
int pivot;

//find middle of array
int middle = last - first;
//compare first middle and last item in array
if((first < last)&&(last > middle)){
if(first < middle){
//middle is median number
pivot = middle;
}else{
//first is median number
pivot = first;
}
}else if((first < middle)&&(middle > last)){
if(first < last){
//last is median number
pivot = last;
}else{
//first is median number
pivot = first;
}
}else{
if(last < middle){
//middle is median number
pivot = middle;
}else{
//last is median
pivot = last;
}
}
}//end choosePivot
/**
* Parition an array for quicksort
* @pre theArray[fist..last] is an array; fisrt <= last.
* @post Partitions theArray[fisrt..last] such that:
*  S1 = theArray[first..pivotIndex-1] < pivot
*       theArray[pivotIndex]         == pivot
*  S2 = theArray[pivotIndex+1..last] >= pivot
* @param theArray The given array
* @param first The first element to cinsider in theArray
* @param last The last element to consider in theArray
* @pivotIndex The index of the pivot after the partition
*/
void partition(int theArray[], int first, int last, int& pivotIndex){
//place pivot int theArray[fisrt]
choosePivot(theArray, first, last);
//copy pivot
int pivot = theArray[first];
//initially, everything but the pivot is unknown
//index of the last item in S1
int lastS1 = first;
//index of first item in unknown
int firstUnknown = first + 1;
//move one item at a time until uknown region is empty
for(; firstUnknown <= last; ++firstUnknown){
//move item from unknown to proper region
if(theArray[firstUnknown] < pivot){
//item from unknown belongs in S1
++lastS1;
tSwap(theArray[firstUnknown], theArray[lastS1]);
}//end if
//place pivot in proper posistion and mark its location
tSwap(theArray[first], theArray[lastS1]);
pivotIndex = lastS1;
}// end partition

}
/**
* Sorts the items in an array into ascending order
* @pre theArray[first..last] is an array
* @post theArray[first..last] is sorted
* @param theArray The given array
* @param first The first element to consider in theArray
* @param last The last element to consider in theArray
*/
void quicksort(int theArray[], int first, int last){
int pivotIndex;

if(first < last){
//create the partition: S1, pivot, S2
partition(theArray, first, last, pivotIndex);

}
}

/**
* The main method
*/
int main(){
int uArray = {5, 3, 7, 9, 1, 0, 4, 8, 6, 2};
quicksort(uArray, 0, 10);
cout << "The sorted array: " << endl;
for(int i = 0; i < 10; i++){
cout << uArray[i] << endl;
}
return 0;
}``````

Any help on how I can finish off the quicksort method, non recursively, so that the quicksort will sort everything? Thanks in advance.

## All 2 Replies

``````void quicksort(int theArray[], int first, int last){
int pivotIndex;

if(first < last){
//create the partition: S1, pivot, S2
partition(theArray, first, last, pivotIndex);
}
}``````

Hmm, methinks you're missing something. ;) Why don't you try starting out with a working recursive quicksort (I posted a code snippet that's a good starting point) and methodically remove the recursion. The tail recursion is easy, as you can just turn it into a loop. The remaining recursion is harder, as you'll need to do something like simulate it with a stack.

I don't recommend writing this algorithm from scratch, because it's very subtle and easy to screw up, especially non-recursively.

Its a homework assignment so that is the only reason I am doing it non recursively. I will try to work through it an d see what I can do. Thanks for the help.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.