jjb123

December 3rd, 2008, 04:37 AM

Hello,

I am trying to write a quick sort program in c++ because I am studying sorting algorithms. Below is the code I have managed to come up with so far, but when I run it the final outputted array seems to be just randomly re-arranged with no pattern that I can tell. I have stared at this for hours now and I am stuck. Any suggestions? Thanks. :D

#include<iostream>

#include<cstdlib>

using namespace std;

//Defines

#define ArraySize 250

#define RandomCap 1000

//Globals

int numbers[ArraySize];

int numbersRaw[ArraySize];

//Prototypes

void arrayPopulate();

void arrayOutput();

void quickSort(int startPosition, int endPosition);

void swap(int& a, int& b);

int splitArray(int pivot, int startPosition, int endPosition);

int main(){

//Generate arrays

arrayPopulate();

//Sort one of the arrays

quickSort(0,ArraySize-1);

//Print array

arrayOutput();

//Wait for return

system("PAUSE");

return 0;

}

void swap(int& a, int& b){

int temp;

temp = a;

a = b;

b = temp;

}

void quickSort(int startPosition, int endPosition){

//Assign the pivot point to the far left element

int pivotPoint = numbers[startPosition];

int splitPoint;

//Make sure there is at least one element

if (endPosition>startPosition){

splitPoint = splitArray(pivotPoint,startPosition,endPosition);

numbers[splitPoint] = pivotPoint;

quickSort(startPosition,splitPoint-1); //Quick sort the first part

quickSort(splitPoint+1,endPosition); //Quick sort the second part

}

}

int splitArray(int pivot, int startPosition, int endPosition){

int leftSide = startPosition;

int rightSide = endPosition;

while (leftSide < rightSide){

while (pivot < numbers[rightSide] && rightSide > leftSide){ //Keep moving until a smaller number is reached, or until we hit the end

rightSide--;

}

swap(numbers[leftSide],numbers[rightSide]); //Swap so that the pivot is to the right of the small one.

while (pivot >= numbers[rightSide] && leftSide < rightSide){ //Keep moving until a larger number is reached, or until we hit the end

leftSide++;

}

swap(numbers[leftSide],numbers[rightSide]);

}

return leftSide;

}

void arrayPopulate()

{

int generateCount;

generateCount = 0;

int tempRand;

while(generateCount<=ArraySize-1){

tempRand = (rand() % RandomCap) + 1;

numbers[generateCount]=tempRand;

numbersRaw[generateCount]=tempRand;

generateCount++;

}

}

void arrayOutput()

{

int outputCount;

outputCount = 0;

while(outputCount<=ArraySize-1){

cout<<outputCount<<":\t"<<numbersRaw[outputCount]<<"\t"<<numbers[outputCount]<<endl;

outputCount++;

}

}

I am trying to write a quick sort program in c++ because I am studying sorting algorithms. Below is the code I have managed to come up with so far, but when I run it the final outputted array seems to be just randomly re-arranged with no pattern that I can tell. I have stared at this for hours now and I am stuck. Any suggestions? Thanks. :D

#include<iostream>

#include<cstdlib>

using namespace std;

//Defines

#define ArraySize 250

#define RandomCap 1000

//Globals

int numbers[ArraySize];

int numbersRaw[ArraySize];

//Prototypes

void arrayPopulate();

void arrayOutput();

void quickSort(int startPosition, int endPosition);

void swap(int& a, int& b);

int splitArray(int pivot, int startPosition, int endPosition);

int main(){

//Generate arrays

arrayPopulate();

//Sort one of the arrays

quickSort(0,ArraySize-1);

//Print array

arrayOutput();

//Wait for return

system("PAUSE");

return 0;

}

void swap(int& a, int& b){

int temp;

temp = a;

a = b;

b = temp;

}

void quickSort(int startPosition, int endPosition){

//Assign the pivot point to the far left element

int pivotPoint = numbers[startPosition];

int splitPoint;

//Make sure there is at least one element

if (endPosition>startPosition){

splitPoint = splitArray(pivotPoint,startPosition,endPosition);

numbers[splitPoint] = pivotPoint;

quickSort(startPosition,splitPoint-1); //Quick sort the first part

quickSort(splitPoint+1,endPosition); //Quick sort the second part

}

}

int splitArray(int pivot, int startPosition, int endPosition){

int leftSide = startPosition;

int rightSide = endPosition;

while (leftSide < rightSide){

while (pivot < numbers[rightSide] && rightSide > leftSide){ //Keep moving until a smaller number is reached, or until we hit the end

rightSide--;

}

swap(numbers[leftSide],numbers[rightSide]); //Swap so that the pivot is to the right of the small one.

while (pivot >= numbers[rightSide] && leftSide < rightSide){ //Keep moving until a larger number is reached, or until we hit the end

leftSide++;

}

swap(numbers[leftSide],numbers[rightSide]);

}

return leftSide;

}

void arrayPopulate()

{

int generateCount;

generateCount = 0;

int tempRand;

while(generateCount<=ArraySize-1){

tempRand = (rand() % RandomCap) + 1;

numbers[generateCount]=tempRand;

numbersRaw[generateCount]=tempRand;

generateCount++;

}

}

void arrayOutput()

{

int outputCount;

outputCount = 0;

while(outputCount<=ArraySize-1){

cout<<outputCount<<":\t"<<numbersRaw[outputCount]<<"\t"<<numbers[outputCount]<<endl;

outputCount++;

}

}