Quicksort-Vorlage funktioniert nicht, und mein Programm reagiert nicht

Question

Ich versuche, einen Vektor von Geburtstagen (mit meiner Implementierung von Quicksort) zu sortieren, und ändern Sie auch die Reihenfolge der zwei Vektoren mit Namen und Geburtsdaten basierend darauf, wie sie sich ändern. Ich habe eine Online-Quelle über die Implementierung von Quicksort verfolgt, bin mir aber nicht ganz sicher, warum das nicht funktionieren wird. Hier ist mein Code:

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 
     } 
    } 
} 

Ich weiß nicht, was ist falsch mit dieser Implementierung. Jede Hilfe wäre willkommen! Danke im Voraus.

Answer 1

Sie setzen eine Rekursion in eine Schleife, so funktioniert die schnelle Sortierung nicht. Und die Anfangs- und Endposition, die an die Rekursionsfunktion übergeben wurden, waren nicht korrekt.

Hier ist die Lösung. Ich habe den Parameter size in end geändert, weil sich die Variable in Ihrem Code so verhält.

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 
    } 
}