Что случилось с моей реализацией quicksort?

Question

только быстрый (хахаха) вопрос относительно моего наивного алгоритма быстрой сортировки:

#include <iostream> 

template <class T> 
void quicksort2(T array[] , int start, int end){ 
    int i = start; 
    int j = end; 
    int temp; 
    int pivot = (end - start)/2; 

    // Partioning 
    while(i <= j){ 

    while(array[i] < array[pivot]){ 
     i++; 
    } 
    while(array[j] > array[pivot]){ 
     j--; 
    } 

    if(i <= j){ 
     temp = array[i]; 
     array[i] = array[j]; 
     array[j] = temp; 
     i++; 
     j--; 
    } 
    } 

    // Sorting partions 
    if(start <= j){ 
    quicksort2(array , start , j); 
    } 
    if(end >= i){ 
    quicksort2(array , i , end); 
    } 
} 

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

Немного предупреждения перед запуском кода, иногда он замерзает мою машину, когда я запускаю код в тестовом массиве.

В любом случае, спасибо за помощь! Кроме того, это не для домашних заданий (Какой класс с алгоритмами сортировки требует, чтобы вы изучили быструю сортировку сразу с места в карьер?)

Answer 1

Я отвечу на ваш вопрос вопросом.

Как вы обрабатываете случай, когда ваш метод вызывается, когда start == end?

Каждый из вас делит ваш подраздел на ось, поэтому каждый рекурсивный прогон имеет 1/2 длины последнего времени. Итак, вы начинаете с сортировки первой половины, затем первой 1/4, затем первой 1/8. В конце концов, вы вызовете метод с start = end = 0. Это делает 0 - 0/2 осью, которая равна 0.

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

Переполнение стека.

Answer 2

Возможно, вам захочется взглянуть на ваше использование '='. Я считаю, что вы можете использовать> = и < = при сравнении с точкой опоры, но при выполнении свопа это не обязательно.

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