Быстрая сортировка
Быстрая сортировка (англ. quicksort) – это надежный и эффективный алгоритм сортировки, который используется не только для учебных целей, но и широко применяется на практике. Быстрая сортировка также называется сортировкой Хоара по имени автора алгоритма Чарльза Хоара. Для большинства массивов этот метод требует приблизительно обменов элементов и сравнений, то есть намного меньше, чем любой другой элементарный метод сортировки. Метод основан на подходе «разделяй и властвуй». Идея алгоритма достаточна проста. Из массива выбирается некоторый опорный элемент р, вокруг которого перемещаются все элементы. Причем элементы меньшие, либо равные р, перемещаются влево от него, а элементы большие, либо равные р – вправо. Далее метод быстрой сортировки рекурсивно запускается для каждой из частей массива. Алгоритм имеет наименьшее время сортировки, если в качестве опорного элемента выбирается средний по номеру элемент, так как в результате разделения части массива имеют одинаковые размеры.
Задача 6.6 Напишите рекурсивный метод быстрой сортировки целочисленного массива.
Объяснение: введем два индекса i и j, в начале алгоритма они указывают, соответственно, на левый и правый конец последовательности. Начнем двигать указатель i с шагом 1 по массиву вперед, пока не будет найден элемент со значением большим или равным значению опорного элемента. Затем аналогичным образом двигаем указатель j от конца массива к началу, пока не будет найден элемент со значением меньшим или равным значению опорного элемента. Далее, если i<=j, меняем найденные элементы местами и продолжаем двигать i и j. Алгоритм разделения заканчиваем тогда, когда индекс i становиться больше индекса j. После разделения все значения до индекса i меньше или равны опорному элементу, а все значения после индекса j больше или равны опорному элементу. Далее рекурсивно вызываем метод быстрой сортировки отдельно для каждой из частей массива. Пример выполнения алгоритма быстрой сортировки массива {5, 0, -10, 9, 15, 100, -12, 3} иллюстрирует рис. 6.5. На рисунке показан только первый шаг рекурсии. На самом деле подмассивы {5, 0, -10, 3, -12} и {100, 15, 9} сортируются затем рекурсивно. Условием завершение рекурсивных вызовов является наличие одного элемента в каждой из частей массива.
public class QuickSort {
static void quickSort (int[] a, int left, int right) {
int i=left, j=right;
int p=a[(left+right)/2]; //опорный элемент
int tmp;
// разделение
do {
while (a[i]<p) i++;
while (a[j]>p) j--;
if (i<=j) {
tmp=a[i]; a[i]=a[j]; a[j]=tmp;
i++; j--;
}
} while (i<=j);
// рекурсивные вызовы сортировки
if (j>left) quickSort(a, left, j);
if (i<right)quickSort(a, i, right);
}
public static void main(String[]args) {
int[] a = {5,0,-10,9,15,100,-12,3};
quickSort(a,0,a.length-1);
System.out.println(java.util.Arrays.toString(a));
}}
Результат:
[-12, -10, 0, 3, 5, 9, 15, 100]
Рис.6.5 – Демонстрация выполнения алгоритма быстрой сортировки