Алгоритм «Быстрой сортировки» (QuickSort). Реализация на Паскале
Описание алгоритма быстрой сортировки:
Идея – более эффективно переставлять элементы, расположенные дальше друг от друга.
1 шаг: выбрать некоторый элемент массива X
1 шаг: выбрать некоторый элемент массива X
2 шаг: переставить элементы так:
A[i] <= X A[i] >= X
A[i] <= X A[i] >= X
3 шаг: так же отсортировать две получившиеся области
78
|
6
|
82
|
67
|
55
|
44
|
34
|
Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов (для этого надо отсортировать массив…).
Разделение: выбрать средний элемент массива (X=67)
Разделение: выбрать средний элемент массива (X=67)
1)
78
|
6
|
82
|
67
|
55
|
44
|
34
|
1)
2)установить L:=1, R:=N
3)увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа)
4)уменьшая R, найти первый элемент A[R], который <= X (должен стоять слева)
5)если L<=R, поменять местами A[L] и A[R] и перейти
к п. 3
Код:
Реализация сортировки Quick Sort на паскале:
procedure QSort ( first, last: integer);
var L, R, c, X: integer;
begin
if first < last then
begin
X:= A[(first + last) div 2];
L:= first;
R:= last;
while L <= R do
begin
while A[L] < X do
L:= L + 1;
while A[R] > X do
R:= R - 1;
if L <= R then
begin
c:= A[L];
A[L]:= A[R];
A[R]:= c;
L:= L + 1;
R:= R - 1;
end;
end;
QSort(first, R);
QSort(L, last);
end;
end.
program qq;
const N = 10;
var A: array[1..N] of integer;
begin
{ заполнить массив }
{ вывести исходный массив на экран }
Qsort ( 1, N ); { сортировка }
{ вывести результат }
end.
Сравнение быстрой сортировки QuickSort и сортировки пузырьком. Количество перестановок(случайные данные):
N | QuickSort | «пузырек» |
10 | 11 | 24 |
100 | 184 | 2263 |
200 | 426 | 9055 |
500 | 1346 | 63529 |
1000 | 3074 | 248547 |