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

 

Быстрая сортировка (англ. 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 – Демонстрация выполнения алгоритма быстрой сортировки