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

Данный алгоритм является самым эффективным методом внутренней сортировки и поэтому имеет название "быстрая сортировка".[*] В этом алгоритме для сортировки элементов массива А[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.