jkd

10-29-2002, 10:47 PM

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? :)

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? :)