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

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


Сегодня я публикую программу, позволяющую быстро отсортировать массив в порядке возрастания. Описание работы программы, исходный код и ссылку на скачивание готовой программы на паскаль, Вы можете увидеть далее.

Итак, структура программы на паскаль быстрой сортировки массива довольно проста. В основе программы лежит метод Чарльза Хоара, английского учёного, специализирующегося в области информатики и вычислительной техники. Наиболее известен как разработчик алгоритма «быстрой сортировки». Кстати, быстрая работа шаблона сайта обеспечивает успехи в seo сайта.

Далее представлена анимированная картинка, поясняющая сортировку.

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



Для того чтобы программа работала необходимо описать ArrayLib. Описание представлено ниже.

unit ArrayLib;

/// Вывод массива
procedure WriteArray<T>(a: array of T);
begin
for var i:=0 to a.Length-1 do
write(a[i],' ');
writeln;
end;

procedure WriteArray(a: array of real);
begin
foreach x: real in a do
write(x:0:1,' ');
writeln;
end;

/// Создание массива и заполнение его случайными числами
procedure CreateRandom(var a: array of integer; n: integer);
begin
a := new integer[n];
for var i:=0 to n-1 do
a[i] := random(100);
end;

procedure CreateRandom(var a: array of real; n: integer);
begin
a := new real[n];
for var i:=0 to n-1 do
a[i] := random*10;
end;

end.


А вот и весь исходный код примера программы на паскаль:


uses ArrayLib;

// Быстрая сортировка
procedure QuickSort(a: array of integer);

// Разделение a[l]..a[r] на части a[l]..a[q] <= a[q+1]..a[r]
function Partition(l,r: integer): integer;
begin
var i := l - 1;
var j := r + 1;
var x := a[l];
while True do
begin
repeat
Inc(i);
until a[i]>=x;
repeat
Dec(j);
until a[j]<=x;
if i<j then
Swap(a[i],a[j])
else
begin
Result := j;
exit;
end;
end;
end;

// Сортировка частей
procedure sort(l,r: integer);
begin
if l>=r then exit;
var j := Partition(l,r);
sort(l,j);
sort(j+1,r);
end;

begin
sort(0,a.Length-1)
end;

const n = 20;

var a: array of integer;

begin
CreateRandom(a,n);
writeln('До сортировки: ');
WriteArray(a);
QuickSort(a);
writeln('После сортировки: ');
WriteArray(a);
end.


Скачать программу: QuickSort.pas
Скачать описание ArrayLib: QuickSort.pas
Дата: 2012-11-08 15:55:49   Просмотров: 13505

Теги: Паскаль Pascal исходник исходники скачать массивы