Читайте также:
|
Ещё один вариант сортировки, более быстрый, чем метод пузырька.
Заключается он в следующем: при каждом просмотре массива находим
минимальный элемент и меняем местами его с первым на первом проходе,
со вторым - на втором и т.д. Не забудьте только, что первый элемент массива должен иметь индекс 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;
Дата добавления: 2015-01-30; просмотров: 286 | Поможем написать вашу работу | Нарушение авторских прав |