Почему моя реализация Quicksort дает переполнение стека?

Question

У меня есть этот код

public static void quicksort(int[] array){ 
    quicksort(array, 0, array.length - 1); 
    } 

    public static void quicksort(int[] array, int min_index, int max_index){ 
    if(array.length <= 1 || min_index >= max_index){ 
     return; 
    } 

    int pivot = array[(max_index + min_index)/2]; 
    int left = min_index; 
    int right = max_index; 

    while(left <= right){ 
     while(array[left] < pivot) 
     left++; 
     while(array[right] > pivot) 
     right--; 
     if(left <= right){ 
     int aux = array[left]; 
     array[left] = array[right]; 
     array[right] = aux; 

     left++; 
     right--; 
     } 
    } 

    if(right > min_index) 
     quicksort(array, min_index, right); 
    if(left < max_index) 
     quicksort(array, left, max_index); 

    } 

который работает довольно хорошо, но если я изменить стержень к pivot = array[0];, он ломает, давая мне StackOverflow исключение. Я пробовал другие значения, и это похоже только на среднюю точку. Почему это происходит?

Answer 1

Это хорошо известная проблема с Quicksort. Для определенных входных сигналов, например. отсортированные (или почти отсортированные) данные, а с плохо выбранными опорными точками Quicksort будет дегенерировать до типа пузырька. Поскольку функция рекурсивна, очень легко создать условие переполнения стека (или выполнить сортировку в O (n) времени). В этом отношении печатные примеры Quicksort печально известны. Quicksort делает хорошее программирование, но вы всегда должны использовать реализацию, предоставляемую вашим компилятором.

Дополнительную информацию о Quicksort см. В статье Wikipedia.