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

Часто удобно иметь данные (особенно, если их много), расположенные в порядке возрастания или убывания. Такое упорядочивание в программировании называется сортировкой. Цель сортировки - облегчить поиск элементов в отсортированном массиве. Как правило, при сортировке выдвигается требование экономии памяти, поэтому сортировка осуществляется без использования вспомогательного массива. Сортировать можно любые данные. Важно только, чтобы их можно было тем или иным способом сравнивать. Существует множество различных алгоритмов сортировки. Одни из них простые, но более медленные, другие - быстрые, но более сложные. Одни сортируют массив каждый раз заново, другие - распознают уже упорядоченные части массива и поэтому работают быстрее. В рамках данного пособия будут рассмотрены следующие алгоритмы сортировки:

• вставки;

• пузырька;

• выбора;

• фон Неймана.

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

Алгоритм. Последовательность чисел разбивают на отсортированную и не отсортированную. Пусть первые k элементов массива уже упорядочены, для определенности, по не убыванию. Берется k+1-й элемент и размещается среди первых k элементов так, чтобы упорядоченными оказались уже k+1 первых элементов. Этот метод применяется при изменяющемся k от 1 до n-1, где n - количество элементов в заданной последовательности.

Пример. Пусть дан массив {4, 5, 2, 3, 9, 1}, который необходимо упорядочить по возрастанию, используя метод вставок.

ш1 4 | 5 2 3 9 1 5 остается на месте.

ш2 4 5 | 2 3 9 1 2 встает в начало массива.

ш3 2 4 5 | 3 9 1 3 встает за 2.

ш4 2 3 4 5 | 9 1 9 остается на месте.

ш5 2 3 4 5 9 | 1 1 встает на первое место.

1 2 3 4 5 9 результат.

Из примера видно, что при поиске подходящего места очередного элемента х из не отсортированного множества, необходимо этот элемент сравнивать с очередным элементом a_j в отсортированном множестве и либо вставлять х, либо продвигаться влево. Таким образом, этот процесс может закончиться при двух различных условиях:

1. найден элемент a_j, меньший, чем х;

2. достигнут левый конец готовой последовательности.

Реализация таких циклов была рассмотрена ранее. Здесь рассмотрим хорошо известный прием фиктивного элемента или барьера. Суть которого состоит в том, что вводится еще один элемент массива с индексом 0, величина которого равна значению элемента из не отсортированной части х, который пытаемся разместить в отсортированном множестве, т.е. а₀ = х, для чего необходимо расширить диапазон индексов в описании массива от 0 до n. И пока х < a_j, продолжаем двигаться по отсортированной части массива.

program sort_insert;

const n = 30;

var a: array [0..n] of integer;

x, i, j: integer;

begin

for i := 1 to n do

read(a[i]); {формирование массива}

for i := 2 to n do

begin

x := a[i]; a[0] := x; j := i-1;

while x < a[j] do {поиск места элемента в упорядоченной части}

begin

a[j + 1] := a[j]; {продвижение по массиву}

j := j - 1

end;

a[j + 1] := x {вставка элемента в нужное место}

end;

for i := 1 to n do

writeln (a[i]);

end.