This is a bit off topic but a few of us my find this interesting, or useful! I'm
pretty much stuck on this one. And here it is...
I am trying to write a quick sort lab in c++ 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).
THANKS!
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.
[c++ code START]
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;
}
//PROBLEM HERE OR IN RANDOM_HOARE_PARTITION
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);
}
}
//PROBLEM HERE OR IN QUICK SORT
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;
}
[c++ code END]
----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.
