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.
Code:
#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++;
}
}
Bookmarks