Массив. Индекс элемента массива. Сортировка массива. Алгоритмы сортировки

Сортировка массива
Алгоритмы сортировки

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

История
Первые прототипы современных методов сортировки появились уже в XIX веке. К 1890 году для ускорения обработки данных переписи населения в США американец Герман Холлерит создал первый статистический табулятор — электромеханическую машину, предназначенную для автоматической обработки информации, записанной на перфокартах[1]. У машины Холлерита имелся специальный «сортировальный ящик» из 26 внутренних отделений.
Перфока́рта — носитель информации из тонкого картона, представляет информацию наличием или отсутствием отверстий в определённых позициях карты.
В дальнейшем история алгоритмов оказалась связана с развитием электронно-вычислительных машин. По некоторым источникам, именно программа сортировки стала первой программой для вычислительных машин.

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

Сортировка простыми обменами или сортиро́вка пузырько́м
(англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов.
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.

Сортировка простыми обменами или сортиро́вка пузырько́м
Var
a :array [1..100] of integer;
I, j, m, k :integer;
begin
for i := 1 to m-1 do
for j := 1 to m-i do
if a[j] > a[j+1] then
begin
k := a[j];
a[j] := a[j+1];
a[j+1] := k
End;
End;
End;
End.