|
Простая сортировка линейного массива.
Часто встречаются задачи, в которых требуется сортировать входные данные, располагая их в порядке возрастания или убывания. Для решения этой задачи были придуманы специальные алгоритмы.
Алгоритмов сортировки много. Они отличаются по скорости работы, по объему требуемой дополнительной памяти и по простоте написания. Мы рассмотрим один из самых простых алгоритмов, который, однако, не является самым эффективным.
Идея алгоритма состоит в том, что в массиве осуществляется поиск самого маленького элемента и этот элемент ставится на первое место, а элемент с первой позиции переставляется туда, где стоял минимальный.
Затем поиск минимального элемента повторяется, но не во всем массиве, начиная с элемента с номером два. Найденный минимальный меняется местами со вторым элементом. Дальнейшая сортировка продолжается по аналогии с уже описанными действиями. В итоге получается отсортированный массив.
Алгоритм сортировки может быть записан следующим образом:
var
а: аrrау[1..100] of integer;
i, j, n, min, t: integer;
begin
// ввод массива
read(n);
for i := 1 to n do
read(a[i]);
// сортировка массива
for i := 1 to n - 1 do
begin
// поиск номера минимального, начиная с позиции i
min := i;
for j := i + 1 to n do
if a[min] > a[j] then
min := j;
t := a[min];
a [min] := a [ i] ;
a [ i ] : = t ;
end;
// вывод массива
for i := 1 to n do
write(a[i],’ ‘) ;
end.
Обратите внимание, что поиск минимального элемента осуществляется n-1 раз. Это происходит потому, что если все элементы массива, кроме одного, уже стоят на своих местах, то и этот единственный тоже будет стоять на своем месте.
Тот же алгоритм можно записать короче, если отказаться от дополнительной переменной для хранения номера минимального элемента массива. В этом случае минимальный будет сразу же записываться в требуемую ячейку массива.
var
a: array[1..100] of integer;
i, j, n, t: integer;
begin
// ввод массива
read(n);
for i := 1 to n do
read(a[i]) ;
// сортировка массива
for i := 1 to n - 1 do
for j := i + 1 to n do
if a[i] > a[j] then
begin
t : = a [ i ] ;
a [ i ] : = a [ j ] ;
a [ j ] : = t ;
end;
// вывод массива
for i := 1 to n do
write(a[i],’ ‘);
end. |