2015-02-04
573
Данный алгоритм является самым эффективным методом внутренней сортировки и поэтому имеет название "быстрая сортировка".[*] В этом алгоритме для сортировки элементов массива А[1],..., А[n] из этих элементов выбирается некоторое значение ключа v в качестве опорного элемента, относительно которого переупорядочиваются элементы массива. Желательно выбрать опорный элемент близким к значению медианы распределения значений ключей так, чтобы опорный элемент разбивал множество значений ключей на две примерно равные части. Далее элементы массива переставляются так, чтобы для некоторого индекса j все переставленные элементы А[1],..., A[j] имели значения ключей, меньшие, чем v, а все элементы A[j + 1],..., А[n] — значения ключей, большие или равные v. Затем процедура быстрой сортировки рекурсивно применяется к множествам элементов А[1],..., A[j] и A[j + 1],..., А[n] для упорядочивания этих множеств по отдельности. Поскольку все значения ключей в первом множестве меньше, чем значения ключей во втором множестве, то исходный массив будет отсортирован правильно.
|
|
|
Задача 7.13. Дан целочисленный массив размерностью 10 элементов. Упорядочить элементы данного массива по возрастанию посредством быстрой сортировки.
Листинг программы
program task4;
uses crt;
const n = 10;
type vector = array [ 1..n] of integer;
var a: Vector;
i, j: integer;
temp: integer;
procedure QuickSort;
procedure sort (l, r: integer);
var i, j, w, x: integer;
begin
i:= l;
j:= r;
x:= a[(l+r) div 2];
repeat
while a[i] < x do
i:=i+1;
while a[j] > x do
j:= j-1;
if i <= j then
begin
w:= a[i];
a[i]:=a[j];
a[j]:=w;
i:= i+1;
j:= j-1;
end;
until i > j;
if l < j then sort(l,j);
if i < r then sort(i,r);
end;
begin
sort (1,n);
end;
begin
clrscr;
randomize;
for i:=1 to n do
begin
a[i]:= random(11)-5;
writeln ('a[', i, ']=', a[i]:3);
end;
quicksort;
writeln ('Отсортированный массив по возрастанию');
for i:= 1 to n do
writeln ('a[', i, ']=', a[i]:3);
readln;
end.
