non recursive quicksort sorts all but one number

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

Open in new window

superwickAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

evilrixSenior Software Engineer (Avast)Commented:
This code just crashes for me. Are you sure you pasted the correct version of the code? Is this a homework exercise?
0
Infinity08Commented:
I cleaned up your algorithm - see the comments I added using

        // <-- these are my comments


#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);           // <--- this doesn't do anything
    //copy pivot
    int pivot = theArray[first];
    
    tSwap(theArray[first], theArray[last]);     // <--- add this
 
    //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;               // <--- first, not first + 1
    
    //move one item at a time until uknown region is empty
    for(; firstUnknown < last; ++firstUnknown){    // <--- < instead of <=
 //move item from unknown to proper region
 if(theArray[firstUnknown] <= pivot){       // <--- <= instead of <
     //item from unknown belongs in S1
     tSwap(theArray[firstUnknown], theArray[lastS1]);
     ++lastS1;                              // <--- has to be after the swap
     
 }//end if
 
    }// end partition
 
 //place pivot in proper posistion and mark its location    // <--- has to be AFTER the for loop
 tSwap(theArray[last], theArray[lastS1]);                   // <--- last instead of first
 pivotIndex = lastS1;                                       // <--- lastS1 instead of theArray[lastS1]
 
    
}
 
/**
 * 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, 9);    // <--- 0 to 9 instead of 0 to 10
    
    cout << "The sorted array: " << endl;
    
    for(int i = 0; i < 10; i++){
 
 cout << uArray[i] << endl;
 
    }
    return 0;
}

Open in new window

0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Infinity08Commented:
The algorithm in pseudo code can be found here :

        http://en.wikipedia.org/wiki/Quicksort
0
trigger-happyCommented:
It may have something to do with the choosePivot function because from what I can see, it does nothing but assign the value of last to an integer pivot which is never read by the entire program. Once the choosePivot program is done, the value of pivot is popped off the stack and so it is never used. Perhaps you wanted to return the value using the return keyword? Another question is why are you creating another qsort algo when the C++ standard algorithm library already uses qsort as ts default sort algorithm?

--trigger-happy
#include <iostream>
#include <algorithm>
#include <iterator>
 
using namespace std;
 
int main(){
     int myarr[10] = {5, 3, 7, 9, 1, 0, 4, 8, 6, 2};
     sort(myarr, myarr+10);
     cout << "Array Elements: ";
     //fancy way of printing elements
     copy(myarr, myarr+10, ostream_iterator<int>(cout, " "));
     cout << endl;
     return 0;
}

Open in new window

0
evilrixSenior Software Engineer (Avast)Commented:
Points well earned I'd say I8 :)
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.