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

Сортировка - это процесс упорядочивания набора данных одного типа по возрастанию или убыванию значения какого-либо признака. При сортировке элементы массива меняются местами таким образом, что их значения оказываются упорядоченными или по возрастанию или по убыванию. В большинстве случаев речь идет о сортировке одномерных массивов.

Сортировка массивов –одно из наиболее важных действий над массивами в системах сбора и поиска информации, т.к. в отсортированных массивах гораздо легче можно найти нужную информацию. Существуют множества способов сортировки массивов. Один из способов сортировки массивов:

Линейная сортировка (сортировка отбором)

Идея линейной сортировки массива заключается в том, чтобы последовательно просматривать все элементы массива, отыскать наименьший (или наибольший) элемент и поменять его местами с первым из рассматриваемых элементов. Затем, просматриваются элементы массива, начиная со второго, снова находить наименьший (или наибольший), который меняется местами со вторым элементом и т.д. Повторяя указные операции с изменением точки отсчета начала поиска минимального (или максимального) из оставшихся элементов, получим отсортированный по возрастанию (или по убыванию) массив.

Пример программы линейной сортировки:

const n = 10;

var

a: array[1..n] of integer;

i,j,m: integer;

begin

for i:= 1 to n do

begin

write('a[',i,']= ');

readln(a[i]);

end;

for i:= 1 to n - 1 do

for j:= i + 1 to n do

begin

if a[i] > a[j] then

begin

m:= a[i];

a[i]:= a[j];

a[j]:= m;

end;

end;

for i:= 1 to n do

writeln(a[i]);

readln;

end.

Сортировка обменами (метод "пузырька")

При сортировке обменами организуется последовательный перебор массива A₁, A₂, A₃, …, A_N и сравнение значений двух соседних элементов на выполнение условия A_i< A_i+1. При выполнении условия элементы меняются местами, и просмотр возобновляется с очередного элемента - A_i+1. По завершении цикла сравнений наибольший элемент массива придвигается на последнее место, а просмотр массива возобновляется с первого элемента при уменьшении на единицу количества просматриваемых элементов (до N-1 элемента), т.к. наибольший из оставшихся элементов после каждого просмотра будет оказываться в конце. Массив будет упорядочен до конца после просмотра, в котором участвуют только первый и второй элементы, следовательно, количество просмотров ограничено значением N-1.

program massor2;

var

j,i,m,n: integer;

a: array[1..10] of integer;

begin

readln(n);

for i:= 1 to n do

readln(a[i]);

for i:= 1 to n-1 do

begin

for j:= 1 to n-1 do

if a[j] > a[j+1] then

begin

m:= a[j];

a[j]:= a[j+1];

a[j+1]:= m;

end;

end;

for i:= 1 to n do

writeln('***** ',a[i]:3);

readln;

end.