Here is my code:
/**
* @file qsort.cpp
*
* @date 11/2/07
*
* This program implements the non recursive version of quicksort
*/
#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 = 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 consider 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 = theArray[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);
quicksort(theArray, first, pivotIndex-1);
quicksort(theArray, pivotIndex+1, last);
}
}
/**
* 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;
}What I get at the end is : 1 0 2 3 4 5 6 7 8 9
Why doesnt the 0 move to the first spot?
