Как работает рекурсия Quick sort?

-1

Ниже перечислены функции быстрого сортировки. Здесь мы берем последний элемент в качестве стержня.Как работает рекурсия Quick sort?

Я понял функцию 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); 
    } 
}

источник

2015-12-13 neOh

Первый (левый, левый, левый, левый, правый). Первый рекурсивный вызов 'qs' находится в левом разделе массива. Рекурсивный вызов правого раздела массива не будет выполняться до тех пор, пока первый вызов не вернется, т. Е. До тех пор, пока левый раздел не будет полностью отсортирован. Другой способ взглянуть на это состоит в том, что вы выполняете обход глубины дерева рекурсии. – beaker

@beaker После первого раздела слева снова разворачивается снова и снова влево, но как насчет правой части раздела левой части (второй раздел слева, справа)? – neOh

@beaker Кроме того, после того, как левая сторона (1-я секция) будет отсортирована, тогда при сортировке правой части qs (a, pi + 1, end) не будет левая функция qs (a, start, pi- 1) также можно назвать? Разве правая сторона (1-й раздел) не будет сортироваться по другому процессу, кроме левой? – neOh

Пример порядка операций для Lomuto схемы разделов, где ось = массива [высокого].

quicksort (массив, low, pivot-1), quicksort (массив, ось поворота + 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

источник

2015-12-13 21:36:51 rcgldr

Отлично! Также как примечание стороны: в вашем примере разделы (слева и справа) всегда имеют одинаковый размер. Это не обязательно так. Например, если у вас есть '8 4 7 6 5 9 2 1 3', то поворот -' 3', а левый раздел имеет 2 элемента, правый 6 элементов –

@SQLOTL - я пытался сделать «симпатичный», Например, в основном для того, чтобы показать сначала первую/левую концепцию глубины. – rcgldr

Да, это «Лучший случай» **. Тогда у вас есть O (n * log (n)). Но реальность различна;) Кстати, ** Худший случай ** заключается в том, что исходный список сортируется в обратном порядке. Затем Quick Sort становится O (n^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. Он очень широк. Вы имеете в виду конкретно в разделении? Как рекурсия обрабатывается? Как биты перемещаются в памяти?

источник

2015-12-13 23:49:10 Fede

ответ

Смежные вопросы