пластическая акробатика

АНДРЕЙ «ORC» СЕРЕГИН

Спецвыпуск: Хакер, номер #071, стр. 071-034-1

(ANDREY.SEREGIN@STP-GROUP.RU)

ПОПУЛЯРНЫЕ АЛГОРИТМЫ

ПРОГРАММИРОВАНИЕ ОКРУЖАЕТ ТЕБЯ СО ВСЕХ СТОРОН. НА РАБОТЕ ТЫ КОДИШЬ С VISUAL STUDIO .NET НОВЫЙ САЙТ ДЛЯ ТВОЕЙ КОНТОРЫ. ДОМА С УПОЕНИЕМ РАЗБИРАЕШЬСЯ В ПРЕМУДРОСТЯХ C ПОД *NIX И В СОТЫЙ РАЗ ПЕРЕКОМПИЛИРУЕШЬ МНОГОСТРАДАЛЬНОЕ ЯДРО

А глубокой ночью, отходя ко сну, ты вдруг вспоминаешь первые уроки информатики, первые программы на алгоритмическом псевдокоде... Но некоторые алгоритмы, хочешь ты или нет, применяются в повседневном программировании и по сей день.

[сортировка.]

Современные методы применяются в основном для сортировки и упорядочивания массивов данных, чаще всего цифровых. Для начала рассмотрим самый простой и самый медлительный алгоритм сортировки – метод пузырька. Он так называется, потому что при такой сортировке самый «легкий» (наименьший) элемент массива постепенно поднимается «наверх» (к началу массива). То есть, просматривая числовой ряд, ищем такую последовательность рядом стоящих чисел, где a > b, и меняем a и b местами. После этого начинаем просматривать массив сначала, уменьшив количество просматриваемых элементов массива на 1. И повторяем это безобразие до тех пор, пока в просмотре не будет участвовать только первое и второе число из массива. Вот процедура, которая осуществляет сортировку массива таким способом:

procedure BubbleMethod (var Arr : Array; const N : Integer);

var

A : Integer;

B : Integer;

Tmp : Double;

begin

A:=0;

while A<=N-1 do

begin

B:=0;

while B<=N-2-A do

begin

if Arr[B]>Arr[B+1] then

begin

Tmp := Arr[B];

Arr[B] := Arr[B+1];

Arr[B+1] := Tmp;

end;

Inc(B);

end;

Inc(I);

end;

end;

Arr – это и входной, и выходной массив, N – число элементов массива. Более быстрый метод сортировки – метод простых вставок (или метод Шелла – не что иное, как модификация метода простых вставок). Есть уже некая упорядоченная последовательность чисел в массиве, где мы располагаем новые сортируемые элементы. В коде это выглядит так:

procedure InsertMethod (var Arr : Array; N : Integer);

var

A : Integer;

B : Integer;

C : Integer;

Tmp : Double;

begin

N := N-1;

A := 1;

repeat

B := 0;

repeat

if Arr[A]<=Arr[B] then

begin

C := A;

Tmp := Arr[A];

repeat

Arr[C] := Arr[C-1];

C := C-1;

until not (C>B);

Arr[B] := Tmp;

B := A;

end

else Inc (B);

until not (B<A);

Inc (A);

until not (A<=N);

end;

Теперь давай посмотрим, какой метод мы можем применить, если нам важна скорость сортировки. Предыдущие методы нам не подходят, так как они хоть и «классика жанра», но быстротой не отличаются. Самый скоростной алгоритм сортировки, известный на сегодняшний день, – это метод бинарных деревьев aka метод Уильяма-Флойда (это не имя и фамилия, а два разных человека). Суть алгоритма в том, что у каждого из элементов массива есть два элемента-потомка, а сам массив считается отсортированным, когда предок > потомка. Хоть метод бинарных деревьев и очень быстр, в реализации он достаточно сложный (смотри листинг 1).

Следующий алгоритм – сортировка методом слияний aka метод фон Неймана. Метод этот заключается в том, что массив делится на упорядоченные группы. Сначала каждая из групп состоит из одного элемента, а затем, соединяя и укрупняя группы их соседями, получаем искомый отсортированный массив. Кстати, обрати внимание на то, что в исходнике для лучшего понимания метода будем использовать второй массив, который имеет тот же размер, что и сортируемый (смотри листинг 2).