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?

This is what I get when I test it?

thwee@thwee-desktop:~$ g++ -Wall pedantic.cc
pedantic.cc: In function ‘void choosePivot(int*, int, int)’:
pedantic.cc:33: warning: unused variable ‘pivot’
thwee@thwee-desktop:~$ ./a.out
Segmentation fault (core dumped)

this is not your code. it is from carrano's book.

So you made an account, just to make this reply on a 3 year old thread? Impressive :icon_wink:
Where exactly does the OP claim that this code is his own?

Edited 6 Years Ago by Nick Evan: n/a

This article has been dead for over six months. Start a new discussion instead.