Методы сортировки массивов

Методы сортировки массивов

Пять методов сортировки массивов, рассмотрены на конкретных примерах: сортировка массива методом пузырька, сортировка методом нахождения минимального элемента, поиск перебором, бинарный поиск.

Сортировка массива методом пузырька - медленная, но если скорость не главное, можно применить и его. Алгоритм очень прост - если два соседних элемента расположены не по порядку, то меняем их местами. Так повторяем до тех пор, пока в очередном проходе не сделаем ни одного обмена, т.е. массив будет упорядоченным. Ниже текст процедуры, реализующей алгоритм сортировки методом пузырька (Arr - массив для сортировки с начальным индексом 0, n - размерность массива)

procedure SortPuz (var Arr : array of Integer; n : Integer);
var
i : Integer;
Temp : Integer;
Flag : Boolean;
begin
repeat
Flag := False;
for i := 0 to n - 1 do
if Arr [i ] > Arr [i + 1] then begin
Temp := Arr [i ];
Arr [i ] := Arr [i + 1];
Arr [i + 1] := Temp;
Flag := True;
end;
until Flag = False;
end;

Сортировка методом нахождения минимального элемента Ещё один вариант сортировки, более быстрый, чем метод пузырька. Заключается он в следующем: при каждом просмотре массива находим минимальный элемент и меняем местами его с первым на первом проходе, со вторым - на втором и т.д. Не забудьте только, что первый элемент массива должен иметь индекс 0.

procedure SortMin (var Arr : array of Integer; n : Integer);
var
i, j : Integer;
Min, Pos, Temp : Integer;
begin
for i := 0 to n - 1 do begin
Min := Arr [i ];
Pos := i;
for j := i + 1 to n do
if Arr [j] < Min then begin
Min := Arr [j];
Pos := j;
end;
Temp := Arr [i ];
Arr [i ] := Arr [Pos];
Arr [Pos] := Temp;
end;
end;

Сортировка массива вставками Более быстрый и оптимальный метод сортировки - сортировка вставками. Суть её в том, что на n-ном шаге мы имеем упорядоченную часть массива из n элементов, и следующий элемент встаёт на подходящее ему место. Имейте в виду - первый индекс массива - 0.

procedure SortInsert (var Arr : array of Integer; n : Integer);
var
i, j, Temp : Integer;
begin
for i := 1 to n do begin
Temp := Arr [i ];
j := i - 1;
while Temp < Arr [j] do begin
Arr [j + 1] := Arr [j];
Dec (j);
if j < 0 then
Break;
end;
Arr [j + 1] := Temp;
end;
end;

Поиск перебором Чтобы найти какие-то данные в неупорядоченном массиве, применяется алгоритм простого перебора элементов. Следующая функция возвращает индекс заданного элемента массива. Её аргументы: массив с первым индексом 0, количество элементов в массиве и искомое число. Если число не найдено, возвращается -1.

function SearchPer (Arr : array of Integer; n, v : Integer) : Integer;
var
i : Integer;
begin
Result := -1;
for i := 1 to n do
if Arr [i ] = v then begin
Result := i;
Exit;
end;
end;

Бинарный поиск При поиске в упорядоченном массиве можно применить гораздо более быстрый метод поиска - бинарный. Суть его в следующем: В начале переменная Up указывает на самый маленький элемент массива (Up := 0), Down - на самый большой (Down := n, где n - верхний индекс массива), а Mid - на средний. Дальше, если искомое число равно Mid, то задача решена; если число меньше Mid, то нужный нам элемент лежит ниже среднего, и за новое значение Up принимается Mid + 1; и если нужное нам число меньше среднего элемента, значит, оно расположено выше среднего элемента, и Down := Mid - 1. Затем следует новая итерация цикла, и так повторяется до тех пор, пока не найдётся нужное число, или Up не станет больше Doun.

function SearchBin (Arr : array of Integer; v, n : Integer) : Integer;
var
Up, Down, Mid : Integer;
Found : Boolean;
begin
Up := 0; Down := n;
Found := False; Result := -1;
repeat
Mid := Trunc ((Down - Up) / 2) + Up;
if Arr [Mid] = v then
Found := True
else
if v < Arr [Mid] then
Down := Mid - 1
else
Up := Mid + 1;
until (Up > Down) or Found;
if Found then
Result := Mid;
end;

Эта запись была добавлена в Понедельник, 5 мая, 2008 - 2:16 В разделы Алгоритмы, Разное. Вы можете подписаться на получение новых комментариев RSS 2.0 feed. Both comments and pings are currently closed.