?
Solved

non recursive quicksort sorts all but one number

Posted on 2008-01-28
5
Medium Priority
?
1,398 Views
Last Modified: 2009-07-29
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

0
Comment
Question by:superwick
  • 2
  • 2
5 Comments
 
LVL 40

Expert Comment

by:evilrix
ID: 20763452
This code just crashes for me. Are you sure you pasted the correct version of the code? Is this a homework exercise?
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 2000 total points
ID: 20763520
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
 
LVL 53

Expert Comment

by:Infinity08
ID: 20763529
The algorithm in pseudo code can be found here :

        http://en.wikipedia.org/wiki/Quicksort
0
 
LVL 14

Expert Comment

by:trigger-happy
ID: 20763539
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
 
LVL 40

Expert Comment

by:evilrix
ID: 20763611
Points well earned I'd say I8 :)
0

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…

593 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question