Как работает рекурсия быстрой сортировки?

Question

Приведенные ниже функции являются реализацией быстрой сортировки. Здесь мы берем последний элемент в качестве оси.

Я поняла partition функция (где ось приходит в свою сортированную позицию), но я не могу понять рекурсивную функцию qs, Функция qs вызывает себя рекурсивно, чтобы решить левую сторону qs(a,start,pi-1) и право раздела по qs(a,pi+1,end),

Делает ли это решение слева, а затем (слева от слева), затем (слева от (слева от слева) и т. Д., А затем влево, влево... вправо и т. Д. Или чередуется, решая слева сторона, а затем правая сторона.

PS: я хочу знать, что происходит внутри компьютера, механизм этой рекурсии быстрой сортировки. Программа работает, но я хочу знать, как она работает.

int partition(int *a, int start, int end)
{   
    int pivot=a[end];
    int pi=start;
    for(int i=start; i<end; i++)
    {
        if(a[i]<=pivot)
        {
            swap(a[i],a[pi]);
            pi++;
        }
    }
    swap(a[pi], a[end]);
    return pi;
}

void qs(int*a, int start, int end)
{
    if(start<end)
    {
        int pi=partition(a,start,end);
        qs(a,start,pi-1);
        qs(a,pi+1,end);
    }
}

Answer 1

Пример порядка операций для схемы разбиения Lomuto, где pivot = array[high].

быстрая сортировка (массив, низкий уровень, пивот-1), быстрая сортировка (массив, главный уровень +1, высокий уровень).

Вертикальная черта, используемая для отображения левого подмассива, оси вращения, правого подмассива.

  11 13 14 12 10  8  9  5  6  4  2  0  1  3  7
   5  6  4  2  0  1  3 11 13 14 12 10  8  9  7 
   5  6  4  2  0  1  3| 7|13 14 12 10  8  9 11
   2  0  1  5  6  4  3 
   2  0  1| 3| 6  4  5
   0  2  1 
   0| 1| 2
               4  6  5
               4| 5| 6
                          10  8  9 13 14 12 11
                          10  8  9|11|14 12 13
                           8 10  9
                           8| 9|10
                                      12 14 13
                                      12|13|14
   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14

Answer 2

Лучший способ понять порядок, в котором происходят события, которые я могу вам предложить, - это распечатать некоторую отладочную информацию на вашем компьютере. qs метод. Для этого я добавил бы дополнительный аргумент ref, в котором я бы посчитал, сколько раз qs вызывается функция и выводит эту информацию рядом с границами решаемого раздела. например

void qs(int*a, int start, int end, int &stepCount)
{
    if(start<end)
    {
        int currentStep = stepCount++;
        cout << "Solving step " << currentStep << " partition from " << start << " to " << end << endl;
        int pi=partition(a,start,end);
        qs(a,start,pi-1,stepCount);
        qs(a,pi+1,end,stepCount);
        cout << "Finished solving step " << currentStep << endl;
    }
}

Не понимаю ваш вопрос PS. Это очень широко. Вы имеете ввиду конкретно в разделе? Как обрабатывается рекурсия? Как биты перемещаются в памяти?