2015-02-24
1581
Сортировка методом простого обмена (методом “пузырька”) является в среднем самой неэффективной. Это обусловлено самой идеей метода, который требует в процессе сортировки сравнивать и обменивать между собой только соседние элементы. Можно существенно улучшить метод сортировки, основанный на обмене. Это улучшение приводит к самому лучшему на сегодняшний день методу сортировки массивов, который можно назвать обменной сортировкой с разделением. Он основан на сравнениях и обменах элементов, стоящих на возможно больших расстояниях друг от друга. Предложил этот метод Ч. А. Р. Хоар в 1962 году. Поскольку производительность этого метода впечатляюща, автор назвал его “быстрой сортировкой”.
Идея метода
1. В исходном неотсортированном массиве выбрать некоторый элемент x (барьерный элемент).
2. Переставить элементы массива таким образом, что слева от x оказались элементы массива, меньшие или равные x, а справа - элементы массива, большие x.
Пусть при этом элемент x попадет в позицию k, тогда массив будет иметь вид: (a[1], a[2],..., a[k-1]), a[k], (a[k+1],..., a[n]).
Каждый из элементов a[1], a[2],..., a[k-1] меньше либо равен a[k], каждый из элементов a[k+1],..., a[n] больше a[k]. Отсюда можно сделать вывод, что элемент a[k] стоит на своем месте. А исходный массив при этом разделится на две неотсортированные части, барьером между которыми является элемент a[k].
Для дальнейшей сортировки необходимо применить пункты 1 и 2 для каждой из этих частей. И так до тех пор, пока не останутся подмассивы, состоящие из одного элемента, то есть пока не будет отсортирован весь массив.
Рассмотрим применение метода “быстрой сортировки” на примере.
Исходный массив состоит из 8 элементов:
8 12 3 7 19 11 4 16
В качестве барьерного элемента будем брать средний элемент массива.
Барьерный элемент - 7. Произведя необходимые перестановки для разделения, получим: (4 3) 7 (12 19 11 8 16)
Теперь элемент со значением 7 стоит на своем месте. Далее сортируем подмассивы, элементы которых заключены в скобки. Этот процесс будем повторять до тех пор, пока не получим полностью отсортированный массив.
Левый подмассив: (3) 4 7 (12 19 11 8 16)
3 4 7 (12 19 11 8 16)
Правый подмассив: 3 4 7 (8) 11 (19 12 16)
3 4 7 8 11 (19 12 16)
3 4 7 8 11 12 (19 16)
3 4 7 8 11 12 (16) 19
3 4 7 8 11 12 16 19
Массив отсортирован полностью.
Алгоритм “быстрой сортировки” можно определить как рекурсивную процедуру, параметрами которой являются нижняя и верхняя границы изменения индексов сортируемой части исходного массива:
program n5;var a: array[1..10] of integer;procedure Init;
{формирование массива из фала}
var f: text;
i: integer;
begin
Assign(f,'g:\s.dat');
Reset(f);
for i:=1 to 10 do read(f,a[i]);
close(f);
end;
procedure Print; {печать массива}
var i: integer;
begin
for i:=1 to 10 do write(a[i]:5);
writeln;
end;
procedure Quik_sorting(m,l: integer);
var i,j,x,w: integer;
begin
i:=m;
j:=l;
x:=a[(m+l) div 2];
repeat
while a[i]<x do inc(i);
while a[j]>x do dec(j);
if i<=j then
begin
w:=a[i]; a[i]:=a[j]; a[j]:=w;
inc(i);
dec(j);
end;
until i>j;
if m<j then Quik_sorting(m,j);
if i<l then Quik_sorting(i,l);
end;
begin {основная программа}
writeln('Массив:');
init;
print;
Quik_sorting(1,10);
writeln('отсортированный массив');
print;
end.
