Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 2 of 2
  1. #1
    jkd
    jkd is offline
    Senior Coder jkd's Avatar
    Join Date
    May 2002
    Location
    metro DC
    Posts
    3,163
    Thanks
    1
    Thanked 18 Times in 18 Posts

    QuickSort in C++

    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:

    Code:
    #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?

  • #2
    New Coder
    Join Date
    Oct 2002
    Location
    middle of nowhere
    Posts
    34
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.
    Last edited by Shawn Curry; 10-30-2002 at 07:02 AM.


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •