Quicksort переполнения стека

Question

я реализовал быструю сортировку массива целых чисел следующим образом:

public void Quicksort(int left, int right) 
{ 
    /* The recursive quicksort algorithm consists of four steps: 
    * 1. If there are one or less elements in the array to be sorted, return immediately. 
    * 2. Pick an element in the array to serve as a "pivot" point. (Usually the left-most element in the array is used.) 
    * 3. Split the array into two parts - one with elements larger than the pivot and the other with elements smaller than the pivot. 
    * 4. Recursively repeat the algorithm for both halves of the original array. 
    */ 

    int pivot = dataTable[left]; 

    int l_hold = left; 
    int r_hold = right; 

    while (left < right) 
    { 
     while ((dataTable[right] >= pivot) && (left < right)) 
      right--; 

     if (left != right) 
     { 
      dataTable[left] = dataTable[right]; 
      left++; 
     } 

     while ((dataTable[left] <= pivot) && (left < right)) 
      left++; 

     if (left != right) 
     { 
      dataTable[right] = dataTable[left]; 
      right--; 
     } 
    } 

    dataTable[left] = pivot; 
    pivot = left; 
    left = l_hold; 
    right = r_hold; 

    if (left < pivot) 
     Quicksort(left, pivot - 1); 

    if (right > pivot) 
     Quicksort(pivot + 1, right); 
} 

Она работает нормально с массивом, скажем, 500 000 случайным образом сгенерированных чисел. Если я заполняю массив с восходящими или нисходящими целыми числами, quicksort вызывает исключение StackOverflowException около 8800 элементов.

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

Метод работает с массивом, который является частью класса и обычно вызывается с (индекс 0, последний индекс - 1). Тысячи благодарностей!

Answer 1

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

Существует способ более подробной информации here.

Answer 2

Необходимо добавить условие остановки.

function() { 

if(value == 0) { 
break; 
} else { 
function()) 
} 

Вы не можете звонить в Quicksort все время. Для этого требуется условие остановки/разрыва.