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

Методы сортировки информации можно отнести к группе алгоритмов, которые образуют «системную» основу для огромного большинства прикладных программ. Сортировка информации – это одна из стандартных процедур, возникающих в процессе решения задач самого различного характера.

В программировании под сортировкой обычно понимают процесс размещения элементов заданного множества объектов в некотором определенном порядке, как правило, в порядке возрастания или убывания.

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

Очевидно, что такое размещение необходимо потому, что с отсортированными данными работать легче, чем с произвольно расположенными. Когда элементы отсортированы, их проще найти, проще производить с ними различные операции. В отсортированных данных легче определить, имеются ли пропущенные элементы; найти общие элементы двух множеств, если оба они отсортированы. Сортировка также является мощным средством ускорения работы практически любого алгоритма, в котором часто нужно обращаться к определенным элементам.

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

Для оценки быстродействия алгоритмов различных методов сортировки, обычно используются два показателя:

· количество сравнений

· количество присваиваний.

Все методы сортировки можно условно разделить на две большие группы

· прямые методы сортировки

· улучшенные методы сортировки

Рассмотрим некоторые методы сортировки.

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

2) Сортировка обменом

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

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

Теория метода:

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

Реализация метода:

Program sort_lin;

const n=10;

M:array[1..n] of byte = (9,11,12,3,19,1,5,17,10,7);

var

i,j,k:byte;

BEGIN

for i:=1 to n-1 do

for j:=i+1 to n do

if M[i]>M[j] then

begin

k:=M[i];

M[i]:=M[j];

M[j]:=k;

end;

for i:=1 to n do

write(a[i]:3);

END.