Шаблон Quicksort не работает, и моя программа не отвечает

Question

Я пытаюсь сортировать вектор дней рождения (используя мою реализацию quicksort), а также изменять порядок двух векторов, содержащих имена и даты рождения, в зависимости от того, как они меняются. Я следовал онлайн-источнику о том, как реализовать quicksort, но я не совсем уверен, почему он не будет работать. Вот мой код:

template <class T> 
void sortBDay(vector<T> &birthday, vector<string> &name, vector<T> &birthdate, int startPos, int size) { // This template sorts all data by their birthday 
    if (startPos < size - 1) { // if the first value is less than the last value 
     T pivotVal = birthday[startPos]; // the pivot value is the vector's first value 
     int pivotPos = startPos; // the pivot position is the vector's starting position 
     for (int pos = startPos + 1; pos <= size; pos++) { // repeat for all values of vector 
      if (birthday[pos] < pivotVal) { // if the current position is less than the starting position 
       swap(birthday[pivotPos + 1], birthday[pos]); 
       swap(birthday[pivotPos], birthday[pivotPos + 1]); // switch the positions 

       swap(name[pivotPos + 1], name[pos]); // and their names 
       swap(name[pivotPos], name[pivotPos + 1]); 

       swap(birthdate[pivotPos + 1], birthdate[pos]); // and their birthdates 
       swap(birthdate[pivotPos], birthdate[pivotPos + 1]); 
       pivotPos++; // then go onto the next one 
      } 
      sortBDay(birthday, name, birthdate, startPos, size - 1); // do the same for upper and lower pivots 
      sortBDay(birthday, name, birthdate, startPos, size + 1); // recursion 
     } 
    } 
} 

Я не знаю, что случилось с этой реализацией. Любая помощь будет оценена! Заранее спасибо.

Answer 1

Вы помещаете рекурсию в цикл, это не так, как работает быстрый сортировка. И начальное и конечное положение, переданные функции рекурсии, неверны.

Вот исправление. Я изменил параметр size на end, потому что так ведет себя переменная в коде.

template <class T> 
void sortBDay(vector<T> &birthday, vector<string> &name, vector<T> &birthdate, int startPos, int end) { // This template sorts all data by their birthday 
    if (startPos < end - 1) { // if the first value is less than the last value 
     T pivotVal = birthday[startPos]; // the pivot value is the vector's first value 
     int pivotPos = startPos; // the pivot position is the vector's starting position 
     for (int pos = startPos + 1; pos < end; pos++) { // repeat for all values of vector 
      if (birthday[pos] < pivotVal) { // if the current position is less than the starting position 
       swap(birthday[pivotPos + 1], birthday[pos]); 
       swap(birthday[pivotPos], birthday[pivotPos + 1]); // switch the positions 

       swap(name[pivotPos + 1], name[pos]); // and their names 
       swap(name[pivotPos], name[pivotPos + 1]); 

       swap(birthdate[pivotPos + 1], birthdate[pos]); // and their birthdates 
       swap(birthdate[pivotPos], birthdate[pivotPos + 1]); 
       pivotPos++; // then go onto the next one 
      } 
     } 

     sortBDay(birthday, name, birthdate, startPos, pivotPos); // do the same for upper and lower pivots 
     sortBDay(birthday, name, birthdate, pivotPos + 1, end); // recursion 
    } 
}