Quick Sort in C++ funktioniert nicht, wenn das mittlere Element als Pivot ausgewählt wurde

Question

Ich habe eine Implementierung von Quick-Sort in C++ versucht. Ich stehe vor einem Problem. Wenn ich den Pivot willkürlich als erstes oder letztes Element auswähle, läuft das Programm gut, aber wenn ich das mittlere Element als Pivot ((Anfang + Ende)/2) wähle, dann ist die Ausgabe nicht vollkommen korrekt. Die meisten Elemente sind in sortierter Reihenfolge, nur einige sind an zufälligen, falschen Orten. Im Folgenden ist mein Code:

#include <iostream> 
#include <cstdlib> 
#include <chrono> 
#include <fstream> 

using namespace std; 
using namespace std::chrono; 

void quickSort(int[], int, int); 
void print(int); 

void print(int n) //prints 50 random numbers in a file 
{ 
    ofstream of("List.txt"); 
    int i; 
    for (i = 0; i < n; i++) 
    { 
     int x = rand() % 50 + 1; 
     of << x << endl; 
    } 
    of.close(); 
} 

int sortf() //calls the quicksort function and sends it array of elements which 
{   //were previously stored in the file and outputs sorted values to another file 
    int arr[50]; 
    int n = 50; 
    ifstream f("List.txt"); 
    int counter = 0; 
    int i; 
    while (!f.eof() && counter < 50) 
    { 
     f >> arr[counter]; 
     counter++; 
    } 
    quickSort(arr, 0, 49); 
    ofstream of("ListOut.txt"); 
    for (i = 0; i < n; i++) 
    { 
     of << arr[i] << endl; 
    } 
} 

void quickSort(int arr[], int start, int end) //applies quicksort algorithm 
{ 
    if (start < end) 
    { 
     int a = start; 
     int b = end; 
     int p = arr[(a + b)/2]; 
     int x = (a + b)/2; 
     int temp; 
     while (a < b) 
     { 
      while (arr[b] > p) 
      { 
       b--; 
      } 
      while (arr[a] <= p && a <= b) 
      { 
       a++; 
      } 
      if (a < b) 
      { 
       temp = arr[b]; //swapping left and right position elements 
       arr[b] = arr[a]; 
       arr[a] = temp; 
      } 
     } 

     temp = arr[b]; //bringing pivot in the middle, so that 
     arr[b] = arr[x]; //elements smaller than pivot are to the left 
     arr[x] = temp; //and elements greater than pivot are to the right 
     quickSort(arr, start, b - 1); 
     quickSort(arr, b + 1, end); 
    } 
} 

int main() 
{ 
    print(50); //printing 50 numbers in the file 
    high_resolution_clock::time_point t1 = high_resolution_clock::now(); 
    sortf(); 
    high_resolution_clock::time_point t2 = high_resolution_clock::now(); 
    auto duration = duration_cast<nanoseconds>(t2 - t1).count(); 
    cout << "\nTime taken:\n" << duration; //outputs time taken for input, sorting and output. 
} 

Die Ausgabedatei nach der Ausführung enthält die folgende Liste der Elemente:

3 16 7 9 25 12 10 12 13 14 24 18 13 16 18 18 21 19 20 20 22 22 23 23 24 27 27 28 30 28 30 30 31 33 34 35 36 41 36 37 37 37 38 41 43 43 
44 44 49 50 

Bitte helfen Sie mir bei der Korrektur von meinem Code, wie ich ziemlich viele Stunden auf dieser verschwendet kleines Problem.

Answer 1

Ich habe die Lösung selbst mit dem Debugger herausgefunden. Lesen Sie den Kommentar in Großbuchstaben, um zu erfahren, welche Änderung vorgenommen wurde, um den Code zu korrigieren. Im Anschluss wird der Arbeitscode für Quicksort Implementierung für 10000 Eingangswerte:

#include <iostream> 
#include <cstdlib> 
#include <chrono> 
#include <fstream> 

using namespace std; 
using namespace std::chrono; 

void quickSort(int[], int, int); 
void print(int); 

void print(int n) //prints 50 random numbers in a file 
{ 
    ofstream of("List.txt"); 
    int i; 
    for (i = 0; i < n; i++) 
    { 
     int x = rand() % 10000 + 1; 
     of << x << endl; 
    } 
    of.close(); 
} 

void sortf(int x) //calls the quicksort function and sends it array of elements which 
{   //were previously stored in the file and outputs sorted values to another file 
    int arr[x]; 
    int n = x; 
    ifstream f("List.txt"); 
    int counter = 0; 
    int i; 
    while (!f.eof() && counter < x) 
    { 
     f >> arr[counter]; 
     counter++; 
    } 
    quickSort(arr, 0, x-1); 
    ofstream of("ListOut.txt"); 
    for (i = 0; i < n; i++) 
    { 
     of << arr[i] << endl; 
    } 
} 

void quickSort(int arr[], int start, int end) //applies quicksort algorithm 
{ 
    if (start < end) 
    { 
     int a = start; 
     int b = end; 
     int p = arr[(a + b)/2]; 
     int x = (a + b)/2; 
     int temp; 
     while (a < b) 
     { 
      while (arr[b] > p) 
      { 
       b--; 
      } 
      while (arr[a] <= p && a <= b) 
      { 
       a++; 
      } 
      if (a < b) 
      { 
       temp = arr[b]; //swapping left and right position elements 
       arr[b] = arr[a]; 
       arr[a] = temp; 
      } 
     } 
     arr[b] = p; //CHANGED THIS *************** 
     quickSort(arr, start, b - 1); 
     quickSort(arr, b + 1, end); 
    } 
} 

int main() 
{ 
    print(10000); //printing 50 numbers in the file 
    high_resolution_clock::time_point t1 = high_resolution_clock::now(); 
    sortf(10000); 
    high_resolution_clock::time_point t2 = high_resolution_clock::now(); 
    auto duration = duration_cast<nanoseconds>(t2 - t1).count(); 
    cout << "\nTime taken:\n" << duration; //outputs time taken for input, sorting and output. 
} 

Vielen Dank für die hilfreiche Ratschläge. Ich würde es sehr schätzen, wenn ihr darauf besteht, einen Debugger zu benutzen. Habe etwas neues gelernt und wirklich hilfreich, jetzt funktioniert mein Code gut, für die Eingabe von 10000 Werten. Prost!