Programming Forums > Application Development > C++

dayrinni · Sep 24th, 2005, 8:41 PM

Hey,

I am trying to write a quick sort lab that uses a randomized Hoare partition function. It doesn't seem to be working correctly. On some data sets, it will sort them very quickly, on others it will loop for infinity.

I am not entirely sure what I am doing wrong. I have went over the hoare partition pseudocode mulitple times, as well as traced through the numbers on paper. I've pretty much spent a good 6 hours today trying to make this work. I also can't find ANY use of a hoare parition on any quick sort code on the internet.

Any help would be great. I feel I am missing 1 key thing (or I did a stupid mistake that I can't find since I have been staring at it for so long).

Note: This compiles and runs on linux. It *should* also work on windows.
Note 2: I passed count for general debugging. I removed all of my debug statements so it looks like count is being passed for no reason.
Note 3: I need to implement the better way of generating random numbers.

(Toggle Plain Text)

using namespace std;
#include <iostream>
#include <ctime>
#include "stdlib.h"

// Maximum of 1 million numbers to sort.
#define MAX_SIZE 1000000

//function def's
void quicksort(int low, int high, int count);
int random_hoare_partition(int low, int high);
int generate_random_number(int min, int max);
void swap(int &first, int &second);

int array[MAX_SIZE];




main(int argc, char *argv[])
{
  	int i;
	int count = 0;
        char c;

       //seed the generator with the current time
       srand(static_cast<unsigned>(time(0)));

  while (cin >> array[count])
    ++count;


  for (i = 0; i < count; ++i)
    cout << array[i] << endl; 




        cout << "Time to sort!" << endl;
        quicksort(0, count-1, count);

        cout << "We sorted, print out the numbers:" << endl;

        for (i = 0; i < count; ++i)
                cout << array[i] << endl;

}

void quicksort(int low, int high, int count)
{
        int pivot;
        if(low < high)
        {
                pivot = random_hoare_partition(low, high);
                quicksort(low, pivot, count);
                quicksort(pivot+1, high, count);
        }
}

int random_hoare_partition(int low, int high)
{
        int pivot;
        int i = low-1;
        int j = high+1;
        bool run = true;
        int index = generate_random_number(low, high);



        pivot = array[index];

        while(run)
        {
                do
                {
                        j = j - 1;
                }
                while (array[j] > pivot);   //find a smaller one
	
		do
                {
                	i = i + 1;
                }
                while(array[i] < pivot);     //find a larger one
		
		if(i < j)
                	swap(array[i], array[j]);
                else
                	return j;


        }

}

//this generates a random number from min to max.
int generate_random_number(int min, int max)
{
        int i;
        int num;

        num  = rand() % (max -min + 1);

        return num;

}

void swap(int &first, int &second)
{
        int temp = first;


        first = second;
        second = temp;


}

using namespace std;
#include <iostream>
#include <ctime>
#include "stdlib.h"

// Maximum of 1 million numbers to sort.
#define MAX_SIZE 1000000

//function def's
void quicksort(int low, int high, int count);
int random_hoare_partition(int low, int high);
int generate_random_number(int min, int max);
void swap(int &first, int &second);

int array[MAX_SIZE];




main(int argc, char *argv[])
{
  	int i;
	int count = 0;
        char c;

       //seed the generator with the current time
       srand(static_cast<unsigned>(time(0)));

  while (cin >> array[count])
    ++count;


  for (i = 0; i < count; ++i)
    cout << array[i] << endl; 




        cout << "Time to sort!" << endl;
        quicksort(0, count-1, count);

        cout << "We sorted, print out the numbers:" << endl;

        for (i = 0; i < count; ++i)
                cout << array[i] << endl;

}

void quicksort(int low, int high, int count)
{
        int pivot;
        if(low < high)
        {
                pivot = random_hoare_partition(low, high);
                quicksort(low, pivot, count);
                quicksort(pivot+1, high, count);
        }
}

int random_hoare_partition(int low, int high)
{
        int pivot;
        int i = low-1;
        int j = high+1;
        bool run = true;
        int index = generate_random_number(low, high);



        pivot = array[index];

        while(run)
        {
                do
                {
                        j = j - 1;
                }
                while (array[j] > pivot);   //find a smaller one
	
		do
                {
                	i = i + 1;
                }
                while(array[i] < pivot);     //find a larger one
		
		if(i < j)
                	swap(array[i], array[j]);
                else
                	return j;


        }

}

//this generates a random number from min to max.
int generate_random_number(int min, int max)
{
        int i;
        int num;

        num  = rand() % (max -min + 1);

        return num;

}

void swap(int &first, int &second)
{
        int temp = first;


        first = second;
        second = temp;


}

dayrinni · Sep 24th, 2005, 11:26 PM

Fixed. I was an idiot and coded the random number generator incorrectly. It works now. At least I was right and it was something simple

OpenLoop · Sep 25th, 2005, 10:01 AM

You think that's stupid, try debugging for 2 hours to find out that you've missed a semi column.

2roll4life7 · Sep 25th, 2005, 12:51 PM

Quote:

Originally Posted by OpenLoop

You think that's stupid, try debugging for 2 hours to find out that you've missed a semi column.

Damn semi columns...

DaWei · Sep 25th, 2005, 2:10 PM

My ex- had a colostomy; now all she HAS is a semi colon.

stevengs · Sep 25th, 2005, 2:17 PM

*groan* .. just when you thought it couldn't possibly get any worse...

Sep 24th, 2005, 8:41 PM	#1
dayrinni Newbie Join Date: Apr 2005 Posts: 17 Rep Power: 0	Quick Sort Hey, I am trying to write a quick sort lab that uses a randomized Hoare partition function. It doesn't seem to be working correctly. On some data sets, it will sort them very quickly, on others it will loop for infinity. I am not entirely sure what I am doing wrong. I have went over the hoare partition pseudocode mulitple times, as well as traced through the numbers on paper. I've pretty much spent a good 6 hours today trying to make this work. I also can't find ANY use of a hoare parition on any quick sort code on the internet. Any help would be great. I feel I am missing 1 key thing (or I did a stupid mistake that I can't find since I have been staring at it for so long). Note: This compiles and runs on linux. It should also work on windows. Note 2: I passed count for general debugging. I removed all of my debug statements so it looks like count is being passed for no reason. Note 3: I need to implement the better way of generating random numbers. (Toggle Plain Text) using namespace std; #include <iostream> #include <ctime> #include "stdlib.h" // Maximum of 1 million numbers to sort. #define MAX_SIZE 1000000 //function def's void quicksort(int low, int high, int count); int random_hoare_partition(int low, int high); int generate_random_number(int min, int max); void swap(int &first, int &second); int array[MAX_SIZE]; main(int argc, char argv[]) { int i; int count = 0; char c; //seed the generator with the current time srand(static_cast<unsigned>(time(0))); while (cin >> array[count]) ++count; for (i = 0; i < count; ++i) cout << array[i] << endl; cout << "Time to sort!" << endl; quicksort(0, count-1, count); cout << "We sorted, print out the numbers:" << endl; for (i = 0; i < count; ++i) cout << array[i] << endl; } void quicksort(int low, int high, int count) { int pivot; if(low < high) { pivot = random_hoare_partition(low, high); quicksort(low, pivot, count); quicksort(pivot+1, high, count); } } int random_hoare_partition(int low, int high) { int pivot; int i = low-1; int j = high+1; bool run = true; int index = generate_random_number(low, high); pivot = array[index]; while(run) { do { j = j - 1; } while (array[j] > pivot); //find a smaller one do { i = i + 1; } while(array[i] < pivot); //find a larger one if(i < j) swap(array[i], array[j]); else return j; } } //this generates a random number from min to max. int generate_random_number(int min, int max) { int i; int num; num = rand() % (max -min + 1); return num; } void swap(int &first, int &second) { int temp = first; first = second; second = temp; } using namespace std; #include <iostream> #include <ctime> #include "stdlib.h" // Maximum of 1 million numbers to sort. #define MAX_SIZE 1000000 //function def's void quicksort(int low, int high, int count); int random_hoare_partition(int low, int high); int generate_random_number(int min, int max); void swap(int &first, int &second); int array[MAX_SIZE]; main(int argc, char argv[]) { int i; int count = 0; char c; //seed the generator with the current time srand(static_cast<unsigned>(time(0))); while (cin >> array[count]) ++count; for (i = 0; i < count; ++i) cout << array[i] << endl; cout << "Time to sort!" << endl; quicksort(0, count-1, count); cout << "We sorted, print out the numbers:" << endl; for (i = 0; i < count; ++i) cout << array[i] << endl; } void quicksort(int low, int high, int count) { int pivot; if(low < high) { pivot = random_hoare_partition(low, high); quicksort(low, pivot, count); quicksort(pivot+1, high, count); } } int random_hoare_partition(int low, int high) { int pivot; int i = low-1; int j = high+1; bool run = true; int index = generate_random_number(low, high); pivot = array[index]; while(run) { do { j = j - 1; } while (array[j] > pivot); //find a smaller one do { i = i + 1; } while(array[i] < pivot); //find a larger one if(i < j) swap(array[i], array[j]); else return j; } } //this generates a random number from min to max. int generate_random_number(int min, int max) { int i; int num; num = rand() % (max -min + 1); return num; } void swap(int &first, int &second) { int temp = first; first = second; second = temp; }

Sep 25th, 2005, 2:10 PM	#5
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	My ex- had a colostomy; now all she HAS is a semi colon. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Sep 25th, 2005, 2:17 PM	#6
stevengs Professional Programmer Join Date: May 2005 Location: Bad Nauheim, Germany Posts: 436 Rep Power: 4	groan .. just when you thought it couldn't possibly get any worse... __________________ -Steven "Is this a piece of your brain?" - Basil Fawlty

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Sep 24th, 2005, 11:26 PM	#2
dayrinni Newbie Join Date: Apr 2005 Posts: 17 Rep Power: 0	Fixed. I was an idiot and coded the random number generator incorrectly. It works now. At least I was right and it was something simple

Sep 25th, 2005, 10:01 AM	#3
OpenLoop Expert Programmer Join Date: May 2005 Location: East Lansing, MI Posts: 663 Rep Power: 4	You think that's stupid, try debugging for 2 hours to find out that you've missed a semi column.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C++

Quick Sort