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

Метод предложен Ч. Э. Р. Хоаром в 1962 году. Быстрая сортировка", хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.

Метод основан на подходе "разделяй - и - властвуй". Общая схема такова:

из массива выбирается некоторый опорный элемент P, например средний элемент, запускается процедура разделения массива, которая перемещает все числа, меньшие, либо равные P, влево от него, а все числа, большие, либо равные P – вправо. Теперь массив состоит из двух подмассивов, причем в левом числа меньшие P (или равные), в правом большие. Для обоих подмассивов, если в подмассиве более двух элементов, рекурсивно запускаем ту же процедуру. В конце получится полностью отсортированная последовательность.

Procedure QuickSort(m, t: Integer);

Var i, j, x, w: Integer;

Begin

i:=m; j:=t; x:=A[(m+t) 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 QuickSort(m, j);

If i<t Then QuickSort(i, t);

End;

Ниже написана программа, которую вы можете запустить на своем компьютере (сделайте это обязательно!)

Const n=10;{размер массива}

Type

list = array[1..n] of integer;

Const

a: list=(9,2,3,7,1,8,5,4,6,10);{заполняем массив числами}

Var i: integer;

{процедура сортировки}

Procedure QuickSort (m, t: Integer);

{ m и t границы сортируемой части массива }

Var i, j, x, w: Integer;

Begin

i:=m; j:=t; x:=A[(m+t) 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 QuickSort(m, j);

If i<t Then QuickSort(i, t);

End;

{Основная программа}

Begin

QuickSort (1,n); {указываем весь массив}

for i:=1 to n do Write(a[i],' '); {вывод массива на экран}

Readln;

end.