We help IT Professionals succeed at work.

non recursive quicksort sorts all but one number

superwick
superwick asked
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;
}

Open in new window

Comment
Watch Question

evilrixSenior 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:
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

CERTIFIED EXPERT
Top Expert 2009

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

        http://en.wikipedia.org/wiki/Quicksort
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

evilrixSenior Software Engineer (Avast)
CERTIFIED EXPERT

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

Explore More ContentExplore courses, solutions, and other research materials related to this topic.