C++ рекурсивный quicksort бесконечный цикл

Question

Итак, у меня возникла проблема с программой на C++, которая быстро сортирует массив целых чисел. Когда у меня есть более шести элементов в моем массиве, сортировка бесконечно петляет по какой-то причине. Я думаю, что я выделил проблему для выбора ключевого значения в миллиметрах, но я не могу разобраться в жизни меня, почему он заставляет его сломаться.

#include<iostream> 
using namespace std; 

int getPivot(int begin,int end){//Takes length of array as input and returns the position of the pivot 
    int len = end-begin; 
    if(len < 3){ 
     return end; 
    }else{ 
     return 2; 
    } 
}; 

void quickSort(int begin, int end, int arr[]){ 
    int pivot = arr[getPivot(begin,end)];//get Pivotal value - If I replace this with just 0 then there are no problems... 
    int tempLeft = begin, tempRight = end; 
    int temp; 
    while(tempLeft <= tempRight){ 
     while(arr[tempLeft] < pivot){//Find a point where there are 2 elements that need to be swapped 
      tempLeft++; 
     } 
     while(arr[tempRight] > pivot){ 
      tempRight--; 
     } 
     if(tempLeft <= tempRight){ 
      temp = arr[tempLeft];//Swap the elements 
      arr[tempLeft] = arr[tempRight]; 
      arr[tempRight] = temp; 
      tempLeft++;//Skip these swapped elements in the sort 
      tempRight--; 
     } 
    } 
    if (begin < tempRight){//Only recurse lower if the new sub array has a length greater than 1 
     quickSort(begin, tempRight, arr); 
    } 
    if (tempLeft < end){ 
     quickSort(tempLeft, end, arr); 
    } 
} 

main() { 
    int array[] = {0,1,2,3,4,5,6}; 
    int length = 7; 
    quickSort(0,length-1,array); 
} 

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

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

Если запустить, как и сейчас, программа будет segfault после цикла бесконечно, но если отсортированный массив будет на один элемент короче, он будет работать нормально. Это заставило меня смутить часами, и я не могу решить, в чем проблема. Если у кого есть какие-либо советы или предложения, они были бы весьма признательны.

Answer 1

quickSort(3,6,arr) всегда будет звонить по телефону quickSort(3,6,arr).

Я думаю, что вы пропустите

int getPivot(int begin,int end) 
{ 
    //Takes length of array as input and returns the position of the pivot 
    int len = end-begin; 
    if(len < 3){ 
     return end; 
    }else{ 
     return 2+begin; // Here 
    } 
}; 

EDIT: Разъяснение

GetPivot(3,6) возвратит 2, вместо этого должен возвращать индекс между 3 и 6.

Answer 2

Можно также использовать медиану трех подхода для вашего стержня. Он немного более прочен.

#include<iostream> 
using namespace std; 

void myswap(int* arr, int left, int right) 
{ 
    int swap = arr[left]; 
    arr[left] = arr[right]; 
    arr[right] = swap; 
} 

int getPivotIndex(int* arr, int begin, int end){ 
    int middle = (begin + end)/2; 

    if (arr[end] < arr[begin]) 
    { 
     myswap(arr, begin, end); 
    } 

    if (arr[middle] < arr[begin]) 
    { 
     myswap(arr, middle, begin); 
    } 

    if (arr[end] < arr[middle]) 
    { 
     myswap(arr, end, middle); 
    } 

    return middle; 
}; 


void quickSort(int begin, int end, int* arr){ 
    int pivot = arr[getPivotIndex(arr, begin, end)]; 
    int tempLeft = begin, tempRight = end; 
    while (tempLeft <= tempRight){ 
     while (arr[tempLeft] < pivot){ 
      tempLeft++; 
     } 
     while (arr[tempRight] > pivot){ 
      tempRight--; 
     } 
     if (tempLeft <= tempRight){ 
      myswap(arr, tempLeft, tempRight); 
      tempLeft++; 
      tempRight--; 
     } 
    } 
    if (begin < tempRight){ 
     quickSort(begin, tempRight, arr); 
    } 
    if (tempLeft < end){ 
     quickSort(tempLeft, end, arr); 
    } 
} 

int main() { 
    int array[] = { 6, 0, 2, 5, 4, 3, 1 }; // Test we are actually sorting 
    int length = 7; 
    quickSort(0, length - 1, array); 

    for (int i = 0; i < length; i++) 
    { 
     std::cout << "array[" << i << "]: " << array[i] << endl; 
    } 
    return 0; 
}