C++ quicksort с хвостовой рекурсией

Question

Hy persons,

У меня возникли проблемы с quicksort в C++. В худшем случае с отсортированным массивом (с растущими или уменьшающимися значениями) я получаю stackoverflow в массивах с ~ 900 элементами. Хвостовая рекурсия была решением я нашел, но им, вероятно, не сделать это прямо здесь, так как им не achiving никаких улучшений:

void quickSort(int *array, int start, int end){ 
    //elementary state 
    if (start + 1 > end){ 
     return; 
    } 

    //partitioning, retuns position of pivotelemnt 
    int wall = partitioning(array, start, end); 

    //recursion 
    quickSort(array, start, wall-1); 
    //tail recursion? 
    return quickSort(array, wall + 1, end); 
}//quickSort 

После this Wikipedia article я просто добавил возвращение к моему последнему вызову QuickSort в качестве первого примера там. Я не думаю, что это делать что-нибудь, хотя ...

редактировать:

int partitioning(int *array, int start, int end){ 

    //partitioningborder 
    int wall = start; 

    for (int i = wall; i < end; ++i){ 
     if (array[i] <= array[end]){ 

      //swap an element if needed 
      int swap = array[i]; 
      array[i] = array[wall]; 
      array[wall] = swap; 

      //increment the partitioningborder 
      wall++; 
     }//if 
    }//for 

    //place pivotelement 
    int swap = array[end]; 
    array[end] = array[wall]; 
     array[wall] = swap; 

     return wall; 
}//partitioning 

Answer 1

Чтобы избежать переполнения стека, код должен сравнить размеры разделов, (стена - начало) против (конец - стена), рекурсию на более мелкий раздел и обратный цикл для более крупного раздела. Это не хвостовая рекурсия. Нечто подобное:

void quickSort(int *array, int start, int end){ 
    while(start < end){ 
     wall = partition(...); // wall = index to pivot 
     // recurse on smaller part, loop on larger part 
     if((wall - start) <= (end - wall)){ 
      quickSort(a, start, wall-1); 
      start = wall+1; 
     } else { 
      quickSort(a, wall+1, end); 
      end = wall-1; 
     } 
    } 
} 

При использование схемы типа раздела Хоары, стены или стены +-может указывать на значение поворота. Вы можете добавить контрольный раздел, чтобы возвращаемый индекс всегда указывал на значение поворота (вместо того, чтобы иногда указывать на 1 до значения поворота).