Под сортировкой в программировании понимается упорядочивание элементов выборки по определенному признаку в определенном порядке. В текущей статье алгоритм сортировки будет рассматриваться на примере одной из самых распространенных структур данных – целочисленного массива.

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

Исходной структурой данных для сортировки будет являться целочисленный массив A (1 до n). Пусть требуется упорядочить элементы этого массива так, чтобы после сортировки они были расположены по не убыванию: a1 <= a2 <= a3 <= .. <= an. Если массив не содержит одинаковых чисел, то можно говорить о сортировке по возрастанию: a1 < a2 < a3 < … < an. Эту же задачу можно также решать при расположении элементов по не возрастанию и не убыванию.

А. Сортировка выбором.

Основным принципом данного приема сортировки является циклический поиск и перестановка минимальных элементов выборки.

Реализуется этот механизм следующим образом:

1. Поиск минимального элемента во всей выборке, его перестановка с первым элементом.

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

Б. Сортировка обменом.

Принцип сортировки:

1. Последовательно просматривая элементы выборки найти такую позицию i, где a(i) > a(i+1) и поменять данные элементы местами, поиск продолжить уже с позиции i+1. Таким образом, наибольший элемент выборки сместится в ее конец.

2. При каждом последующем действии поиск опять начинается с первого элемента, однако, заканчивается на элемент раньше предыдущего. Массив будет полностью упорядочен после просмотра, в котором участвуют только два элемента: a(1) и a(2). Данный метод может быть значительно оптимизирован при учете еще одного фактора – количества перестановок в момент каждого просмотра массива. Если на каком-либо шаге не было выполнено ни одной перестановки, это означает, что массив уже отсортирован и дальнейшие просмотры не требуются. Таким образом в реальных условиях, для выполнения сортировки таким методом может понадобиться значительно меньше проходов, чем (n-1).

В. Сортировка включением.

Принцип метода: предполагается, что элементы a(1), a(2) … a(j-1) уже упорядочены, элемент a(j) должен быть вставлен на соответствующее место, не нарушая упорядоченности. Для этого элемент a(j) по очереди сравнивается с a(j-1), a(j-2) и так далее, до тех пор, пока не будет обнаружено, что элемент a(j) следует вставить между a(i) и a(i+1) (i-номер элемента в последовательности a(1) … a(j-1)), тогда элементы a(i+1), a(i+2) и т.д. сдвигаются на одну позицию вправо, а переставляемый элемент помещается на место (i+1).


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

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

2. Задача поиска места заданного элемента в упорядоченном массиве. Дан упорядоченный по неубыванию массив целых чисел и число “b”. Необходимо найти такое место для “b” в массиве, чтобы после его вставки на это место упорядоченность массива не нарушалась. При равенстве значений “b” ставится на ближайшее к началу массива место.
Для решения данной задачи оптимально подходит метод половинного деления, иначе называемый бинарным поиском. Алгоритм метода: первоначальные границы поиска – [i=1;j=n]. Далее, до тех пор, пока не найдется нужный элемент или границы поиска не перекроются, сдвигаем их следующим образом: сравниваем “b” с a(m), где m – целая часть среднего арифметического границ, если a(m) < b, то меняем прежнюю нижнюю границу на m+1, а верхнюю оставляем без изменения, в противном случае (a(m)>b) оставляем без изменения нижнюю границу, а верхнюю меняем на m. Когда границы станут равными, выполнение алгоритма заканчивается и таким образом получается номер места, на которое вставляется элемент “b”.

3. Задача поиска заданного элемента в массиве. Дан упорядоченный по возрастанию массив и число “b”, определить такое “k”, что a(k) == b.
Для решения данной задачи также можно использовать бинарный поиск. Алгоритм метода в данном случае: первоначальные границы – [i=1;j=n]. Далее, до тех пор, пока не найдем нужный элемент или границы не пересекутся, сдвигаем их следующим образом: сравниваем “b” с a(m) (m – определяется аналогично задачи 2), если a(m) = b, то k = m (и выход из алгоритма), иначе, если a(m)<b, то сдвигаем левую границу, то i=m+1, иначе (a(m)>b) сдвигаем правую границу j=m-1.