I'm trying to write a quicksort function that sorts within a range using a start and end parameter. The problem is, I need to use a random pivot in the quicksort and my random number generator is throwing an exception. I have looked everywhere to see what I'm doing wrong but cannot figure it out at all.
Here is my function(s)
static random_device rd;
static mt19937 rng(rd());
template <typename T>
int partition(T array[], const int start, const int end){
uniform_int_distribution<int> distribution(start, end);
int randIndex = distribution(rng);
swap(array[randIndex], array[end]);
auto pivot = array[end];
int i = start + 1;
for (int j = start; j < end; j++)
{
if (array[j] < pivot)
{
i++;
swap(array[i], array[j]);
}
}
swap(array[i + 1], array[end]);
return i + 1;
}
template <typename T>
void quickSort(T array[], const int start, const int end) {
if (start < end)
{
int pivotIndex = partition(array, start, end);
quickSort(array, start, pivotIndex - 1);
quickSort(array, pivotIndex + 1, end);
}
}
I want the pivot index to be created using the RNG but it breaks before the pivot index can be initialized. Any ideas as to why this is occurring?
Aucun commentaire:
Enregistrer un commentaire