I'm working on a Random Quick Sort program in C++, but for some reason, by program is segfaulting, and I'm a little lost as to why.
I'm pretty sure it has something to do with my hoarePartition function, getting caught in a while loop, but I'm not really sure where the problem is.
Any help on solving this problem would be very helpful!
#import <iostream>
#import <cstdlib>
#import <random>
#import <time.h>
#include <ctime>
#include <boost/timer.hpp>
void swap(int& first, int& second)
{
int temp = first;
first = second;
second = temp;
}
int hoarePartition(int* array, int leftIndex, int rightIndex)
{
int partition = array[leftIndex];
int i = leftIndex;
int j = rightIndex + 1;
while (i < j)
{
while (array[i] < partition && i <= j)
{
i = i + 1;
}
while (array[j] > partition && j > i)
{
j = j - 1;
cout << j << endl;
}
swap(array[i], array[j]);
}
swap(array[i], array[j]);
swap(array[leftIndex], array[j]);
return j;
}
void randomQuickSort(int* array, int leftIndex, int rightIndex)
{
if (leftIndex < rightIndex)
{
int q = rand() % (rightIndex - leftIndex) + leftIndex;
swap(array[leftIndex], array[q]);
int s = hoarePartition(array, leftIndex, rightIndex);
randomQuickSort(array, leftIndex, s-1);
randomQuickSort(array, s+1, rightIndex);
}
}
int main(int argc, char** argv)
{
srand(time(NULL));
int size = atoi(argv[1]);
int* array = new int[size];
for (int i = 0; i < size; ++i)
{
array[i] = (100.0 * rand()) / RAND_MAX;
}
boost::timer t;
randomQuickSort(array, 0, size);
std::cout << t.elapsed() << endl;
delete[] array;
return 0;
}
Aucun commentaire:
Enregistrer un commentaire