We help IT Professionals succeed at work.

# non recursive quicksort sorts all but one number

on
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;
}
``````
Comment
Watch Question

## View Solution Only

Senior Software Engineer (Avast)
CERTIFIED EXPERT

Commented:
This code just crashes for me. Are you sure you pasted the correct version of the code? Is this a homework exercise?
CERTIFIED EXPERT
Top Expert 2009
Commented:

// <-- 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;
}
``````
CERTIFIED EXPERT
Top Expert 2009

Commented:
The algorithm in pseudo code can be found here :

http://en.wikipedia.org/wiki/Quicksort

Commented:
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;
}
``````
Senior Software Engineer (Avast)
CERTIFIED EXPERT

Commented:
Points well earned I'd say I8 :)