Вы здесь

Быстрая сортировка

Исходный код на C++: 

Теория

Алгоритм быстрой сортировки работает на принципе «разделяй и властвуй». Он делит сортируемый массив на части. После этого части массива сортируются независимо друг от друга. В качестве разделяющего элемент выберем элемент in[l](левая граница массива). Далее сравниваем элемент in[i=l](левая граница массива) с in[j=r](правая граница массива) и двигаемся к концу массива i++. Просмотр элементов осуществляется слева направо. Если элементы стоят не по порядку, осуществим их перестановку и изменим направление просмотра массива справа налево. Данный процесс продолжается до тех пор, пока левый индекс будет меньше правого. Изменяем границы сортировки массива и рекурсивно вызываем функцию сортировки. Этот процесс повторяется пока, не достигнем базы рекурсии (if(left>=right)return). Пример работы алгоритма: дан входной массив чисел 3,5,11,73,1,-9,5,2. Первый шаг работы алгоритма.
i=0,j=7 сравниваем 3 с 2. Выполним перестановку элементом массива и изменяем направление просмотра. Массив равен 2,5,11,73,1,-9,5,3.
i=1,j=7 сравниваем 5 с 3. Выполним перестановку элементом массива и изменяем направление просмотра. Массив равен 2,3,11,73,1,-9,5,5.
i=1,j=6 сравниваем 3 с 5. Данную пару оставим без изменения. Массив равен 2,3,11,73,1,-9,5,5.
i=1,j=5 сравниваем 3 с -9. Выполним перестановку элементом массива и изменяем направление просмотра. Массив равен 2,-9,11,73,1,3,5,5.
i=2,j=5 сравниваем 11 с 3. Выполним перестановку элементом массива и изменяем направление просмотра. Массив равен 2,-9,3,73,1,11,5,5.
i=2,j=4 сравниваем 3 с 1. Выполним перестановку элементом массива и изменяем направление просмотра. Массив равен 2,-9,1,73,3,11,5,5.
i=3,j=4 сравниваем 73 с 3. Выполним перестановку элементом массива и изменяем направление просмотра. Массив равен 2,-9,1,73,3,11,5,5.
i=3,j=3 массив равен 2,-9,1,3,73,11,5,5. В итоге получим после первого шага (рис. 1).

После первого шага работы алгоритма
Рис. 1 Быстрая сортировка. Шаг 1.

Далее сократим правую границу l=0,r=2 и повторим процесс. Получим после второго шага (рис. 2).

После второго шага работы алгоритма
Рис. 2 Быстрая сортировка. Шаг 2.

Продолжая итерационный процесс, мы получим отсортированный массив.

Программная реализация

void sort_quick(int left,int right,double *mass)
{
int i,j;
bool f;
double t;
if(left>=right)return ;
for(i=left,j=right,f=true;i<j;f?j--:i++)
if(mass[i]>mass[j])
{t=mass[i];mass[i]=mass[j];mass[j]=t;f=!f;}
sort_quick(left,i-1,mass);
sort_quick(i+1,right,mass);
}