Сортировка массива

Сортировка массива является важнейшим понятием информатики. Сортировка — это процесс упорядочивания набора данных одного типа по возрастанию или убыванию значения какого-либо признака.

Сортировка методом «пузырька»

Один из самых популярных методов сортировки основан на том, что в процессе выполнения алгоритма более «легкие» элементы массива постепенно «всплывают», подобно процессу движения пузырьков в резервуаре с водой. Сортировка методом «пузырька» основана на выполнении в цикле операций сравнения и, при необходимости, обмена соседних элементов. Для перестановки элементов в массиве по убыванию их значений необходимо при их сравнении заменить знак в условном операторе > на <.

const
        n = 20;
var
        i,j:byte;
        buff:integer;
        a:array[1..n] of integer;
begin
randomize;
for i := 1 to n do
begin
        a[i] := random(100);
        write(a[i]:3)
end;
for j := n downto 2 do
        for i := 1 to j — 1 do
                if a[i] > a[i + 1]  then
                begin
                        buff := a[i];
                        a[i] := a[i + 1];
                        a[i + 1] := buff;
                end;
writeln;
for i := 1 to n do
        write(a[i]:3);
writeln;
readln
end.

Тестовый пример

21 16 89 31 30 86 73 70 83 37 22 84 22 91 76 15 24 82 22 56
15 16 21 22 22 22 24 30 31 37 56 70 73 76 82 83 84 86 89 91

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

Рассмотренный выше метод является простым, но не эффективным. Значительно быстрее работает алгоритм сортировки Хоара, называемый также «Быстрой сортировкой», «сортировкой с разделением» или qsort (по имени реализации в стандартной библиотеке языка Си), разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году. Данный алгоритм использует рекурсивный вызов процедуры. Подробное описание: https://ru.wikipedia.org/wiki/Быстрая_сортировка (здесь же приводится вариант процедуры с вложенной процедурой). См. также Занятие 17 на сайте А. Н. Середы, где очень подробно рассматривается этот алгоритм: http://dolschool5.narod.ru/dist/inf.htm Пример использования процедуры с быстрой сортировкой.

uses
    crt;
const
	count=20;
type
	Tint = integer;
	vector=array[1..count] of Tint;
var
	k:integer;
	mass:vector;
// Процедура быстрой сортировки
procedure sort(var mass:vector; first,last:integer);
var
	i,j:integer;
	x,buf:Tint;
begin
	// Получаем границы
	i:=first; j:=last;
	// Находим средний элемент
	x:=mass[(first + last) div 2];
	repeat
		// Изменить порядок сортировки можно
		// поменяв > < в этих двух строках
		// Поиск максимального слева
		while mass[i] < x do inc(i);
		// Поиск минимального справа
		while x < mass[j] do dec(j);
		if i <= j then
		begin
			// Поменяем их местами
			buf:=mass[i];
			mass[i]:=mass[j];
			mass[j]:=buf;
			// и продолжим
			inc(i); dec(j);
		end;
	until i > j;
	// Рекурсивные вызовы процедуры
	if first < j then
		sort(mass,first,j);
	if i < last then
		sort(mass,i,last);
end;
begin
    clrscr;
	// Заполнение и вывод исходного массива
	for k:=1 to count do
	begin
		mass[k]:=random(100);
		write(mass[k]:3)
	end;
	// Вызов процедуры сортировки; отправляем массив и границы
	sort(mass, 1, count);
	writeln;
	// Вывод отсортированного массива
	for k:=1 to count do
	begin
		write(mass[k]:3)
	end;
end.

Эффективность данного алгоритма будет возрастать (в сравнении с пузырьковой сортировкой) с увеличением числа элементов массива.

Добавить комментарий