QuickSort in C++

[jkd]

Today in AP Computer Science lab, we wrote quick sort! yay

There is a slight problem with my implementation though, and neither the teacher nor I could figure out exactly why. He told me to try running it on another computer simply because there is nothing he could find wrong. The problem still persists, so I'm wondering if anyone here can pick up the mistake:


#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include "apvector.h"

void swap(int &, int &);

void fillArray(apvector<int> &, int);
void printArray(const apvector<int> &);

void insertionSort(apvector<int> &, int, int);
void iSort(apvector<int> &);

int partitionQuick(apvector<int> &, int, int);
void quickSort(apvector<int> &, int, int);
void qSort(apvector<int> &);

int main() {
srand(time(NULL));

apvector<int> rArray;
fillArray(rArray, 300); // Change 300 to whatever number
printArray(rArray);
cout << "-------------------------------------" << endl;
qSort(rArray);
printArray(rArray);

return 0;
}

void swap(int & a, int & b) {
int temp = a;
a = b;
b = temp;
}

void fillArray(apvector<int> & arr, int length) {
arr.resize(length);
for (int i = 0; i < arr.length(); i++)
arr[i] = rand();
}

void printArray(const apvector<int> & arr) {
cout << "{ ";
for (int i = 0; i < arr.length(); i++) {
cout << arr[i];

if (i < arr.length() - 1)
cout << ", ";
}
cout << " }" << endl;
}

void iSort(apvector<int> & arr) {
insertionSort(arr, 0, arr.length());
}
void insertionSort(apvector<int> & arr, int min, int max) {
int temp, smallest;
smallest = min;

// set a sentinel value
// adds n steps, but saves slightly more than half the required comparisons
for (int a = min; a < max; a++) {
if (arr[a] < arr[smallest])
smallest = a;
}
swap(arr[min], arr[smallest]);

for (int i = min + 1; i < max; i++) {
temp = arr[i];
int j = i - 1;
while (temp < arr[j]) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}

int partitionQuick(apvector<int> & arr, int low, int high) {
if (high - low <= 10) {
// QuickSort is slower on smaller lists then Insertion Sort,
// so let's use Insertion Sort!
insertionSort(arr, low, high);
return -1;
}
else {
int first = arr[low];
while (low < high) {
while (arr[high] > first) high--;
while (arr[low] < first) low++;
if (low < high)
swap(arr[low], arr[high]);
}
return high;
}
}

void quickSort(apvector<int> & arr, int a, int b) {
if (a < b) {
int pivot = partitionQuick(arr, a, b);
if (pivot > -1) {
quickSort(arr, a, pivot - 1);
quickSort(arr, pivot + 1, b);
}
}
}

void qSort(apvector<int> & arr) {
quickSort(arr, 0, arr.length()-1);
}


You only need to really look at the last 3 functions.

Now, here is the problem:

It works fine on apvector's with length() less than 300 or 400 or so. Anything higher, my CPU usage goes up to a 100%, and does nothing.
The trick is that it does work on smaller arrays, but not larger ones, which means the algorithm itself works fine. And my 1ghz Duron with 256mb of DDR should be able to QuickSort a 500 element list in a second, if not less, because I can sort a 10000 element list via Insertion sort in about the same time (which is slower than QuickSort in with large amounts of data).

The program's memory usage stays at a constant amount of RAM too, which means there isn't a memory leak anywhere... so I'm just probably swapping the pivot around not accomplishing anything... but it works fine on smaller numbers...

Any ideas? :)

[Shawn Curry]

That's what i'm thinking too. If making this numbers class has taught me anything its that when your passing a lot of variables to several different functions, certain things can lead the program to make just one decision that you didnt expect. Try putting a std::cout after each if else conditional just telling what decision is being made, so its not invisible anymore. Even if this doesnt fix it, it will steer you in the right direction.

BTW, if you use one of the standard libraries:

#include <iostream> //normal way
#include <iostream.h>// says:

#include <iostream>
using namespace std;

so you are avoiding using the namespace qualifier. Probably 99% of the time you'll be safe doing that, but they put it all inside the namespace to segregate it from your stuff.