jeudi 19 février 2015

C++ Random Quick Sort SegFault

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