jeudi 5 octobre 2023

Problems with mt19937 random number generator in quicksort function

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