Non-recursive quicksort help

[JaksLax]

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[10] = {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.

[Narue]

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.

[JaksLax]

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.