Как работает алгоритм быстрой сортировки?

Question

[netrox]

Можете подробно описать принцип работы данного алгоритма ?

int partition (int[] array, int start, int end) 
   {
       int marker = start;
       for ( int i = start; i <= end; i++ ) 
       {
           if ( array[i] < array[end] ) 
           {
               int temp = array[marker]; // swap
               array[marker] = array[i];
               array[i] = temp;
               marker += 1;
           }
       }
       return marker - 1;
   }

   void quicksort (int[] array, int start, int end)
   {
       if ( start >= end ) 
       {
           return;
       }
       int pivot = partition (array, start, end);
       quicksort (array, start, pivot-1);
       quicksort (array, pivot+1, end);
   }

Comments

[VovanZ]

Вы хотите, чтобы вам пересказали статью с Википедии, или что?

[netrox]

VovanZ: я вычитал из книги принцип работы алгоритма но конкретно код я не понял

Answer 1

[Денис Загаевский]

Вот вам даже видео https://youtu.be/ywWBy6J5gz8
А так читайте в интернетах.

Answer 2

[Владимир Олохтонов]

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

Comments

[netrox]

Мне непонятны последние две рекурсивный функции:
quicksort (array, start, pivot-1);
quicksort (array, pivot+1, end);
Как произойдёт вызов функции "quicksort (array, pivot+1, end);" если до неё происходит такая же рекурсия ,которая будет вызывать куиксорт заново .Фактически до вызова функции "quicksort (array, pivot+1, end);" дело даже не дойдёт, а тогда зачем она там ?

[VovanZ]

netrox: почему не дойдёт? Дойдёт, после того, как `quicksort (array, start, pivot-1);` полностью отработает.

[Владимир Олохтонов]

netrox: каждый вызов происходит на своей, изолированной от остальных вызовов, части массива. Они не пересекаются.

[Владимир Олохтонов]

netrox: А, я понял в чем у вас проблема :) Рекурсия обязательно должна иметь условие выхода, в данном случае, мы можем делать возврат как только длина сортируемого участка становится равна 1 (или сортировать пузырьком при небольшом числе элементов, 8 например).