Быстрая сортировка Seg Faulting

Question

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

template<class ItemType> 
void sortFirstMiddleLast(ItemType arr, unsigned int first, unsigned int mid, unsigned int last) 
{ 
    if (arr[first] > arr[mid]) { swap(arr[first], arr[mid]); } 
    if (arr[mid] > arr[last]) { swap(arr[mid], arr[last]); } 
    if (arr[first] > arr[mid]) { swap(arr[first], arr[mid]); } 
} 

template<class ItemType> 
int partition(ItemType* arr, unsigned int first, unsigned int last) 
{ 
    unsigned int mid = first + (last - first)/2; 
    sortFirstMiddleLast(arr, first, mid, last); 
    swap(arr[mid], arr[last - 1]); 
    unsigned int pivotIndex = last - 1; 
    ItemType pivot = arr[pivotIndex]; 

    unsigned int indexFromLeft = first + 1; 
    unsigned int indexFromRight = last - 2; 
    cout << indexFromLeft << endl; 
    cout << indexFromRight << endl; 

    bool sorted = false; 

    while (!sorted) 
    { 
     while (arr[indexFromLeft] < pivot) { indexFromLeft += 1; } 
     while (arr[indexFromRight] > pivot) { indexFromRight -= 1; } 

     if (indexFromLeft < indexFromRight) 
     { 
      swap(arr[indexFromLeft], arr[indexFromRight]); 
      indexFromLeft += 1; 
      indexFromRight -= 1; 
     } 
     else { sorted = true; } 
    } 

    swap(arr[pivotIndex], arr[indexFromLeft]); 
    pivotIndex = indexFromLeft; 

    return pivotIndex; 
} 

template<class ItemType> 
void quickSort(ItemType* arr, unsigned int first, unsigned int last) 
{ 
    // Create the partition: S1 | pivotIndex | S2 
    int pivotIndex = partition(arr, first, last); 

    // Sort subarrays S1 and S2 
    quickSort(arr, first, pivotIndex - 1); 
    quickSort(arr, pivotIndex + 1, last); 
} // end quickSort 

int main() 
{ 
    string* a = new string[27]; 
    a[0] = "B"; 
    a[1] = "Z"; 
    a[2] = "Y"; 
    a[3] = "X"; 
    a[4] = "W"; 
    a[5] = "V"; 
    a[6] = "U"; 
    a[7] = "T"; 
    a[8] = "S"; 
    a[9] = "R"; 
    a[10] = "Q"; 
    a[11] = "P"; 
    a[12] = "O"; 
    a[13] = "N"; 
    a[14] = "M"; 
    a[15] = "L"; 
    a[16] = "K"; 
    a[17] = "J"; 
    a[18] = "I"; 
    a[19] = "H"; 
    a[20] = "G"; 
    a[21] = "F"; 
    a[22] = "E"; 
    a[23] = "D"; 
    a[24] = "C"; 
    a[25] = "B"; 
    a[26] = "A"; 
    quickSort(a, 0, 26); 
    for (int i = 0; i < 26; i++) 
     cout << a[i] << " "; 
    cout << endl; 

    return 0; 
}; 

Answer 1

У вас нет базовых чеек в вашей рекурсии. Если ваш код не разбился при выполнении фактической работы, по крайней мере, он был бы захвачен бесконечной рекурсией.

Принцип рекурсии состоит в том, что вы постепенно уменьшаете свою проблему до меньших проблем, пока не достигнете тривиальной проблемы, которую вы можете решить без рекурсии: базовый случай. В вашем случае это будет, когда длина вашего подматрица для сортировки меньше или равна 3. В этом случае вы можете тривиально сортировать суб-массив, просто называя свою функцию sortFirstMiddleLast.

В частности, ваша ошибка сегментации происходит от «indexFromRight = last - 2», что становится отрицательным, вызывая недоиспользование. Это потому, что ваша логика больше не работает, когда сортировка подмассивов становится малой. Но, как было сказано ранее: нет необходимости работать, просто реализуйте эти тривиальные случаи без разделения и рекурсии.