Quick Sort in C++ не работает, когда средний элемент выбран как ось

Question

Я попытался выполнить быструю сортировку в C++. Я столкнулся с проблемой. Если я произвольно выбираю опорный элемент в качестве первого или последнего элемента, программа работает нормально, но если я выберу средний элемент в качестве поворота ((beg + end)/2), то вывод будет не совсем правильным. Большинство элементов находятся в упорядоченном порядке, только некоторые из них в случайных, неправильных местах. Ниже мой код:

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

Выходной файл после выполнения содержит следующий перечень элементов:

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 

Пожалуйста, помогите мне в исправлении моего кода, как я потратил довольно много часов на это немного проблема.

Answer 1

Я сам выяснил решение, используя отладчик. Обратите внимание на комментарий в верхнем регистре, чтобы узнать изменения, внесенные для исправления кода. Ниже приведен рабочий код для реализации Quicksort для 10000 входных значений:

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

Спасибо за полезный совет. Очень ценю, что вы, ребята, настаиваете на использовании отладчика. Узнал что-то новое и действительно полезное, теперь мой код работает отлично, для ввода 10000 значений. Ура!