Паскаль. P.17. Массивы. Продолжение

Самой распространенной процедурой над массивами является сортировка элементов массива. Существуют множество алгоритмов сортировки, каждый из которых имеет как свои достоинства, так и свои недостатки. Рассмотрим некоторые из них. Сортировка методом прямого включения. Массив мысленно делится на исходный и отсортированный. Проходим мысленно по всем элементам исходного массива и перемещаем текущий элемент на то место, где он должен быть в отсортированном массиве. Поскольку, все действия производятся в одном, исходном массиве, то при перемещении элемента, все элементы между позициями, куда вставляем и откуда вставляем, сдвигаются на один вправо (сортировка по возрастанию, каждый элемент перемещается влево на несколько позиций). Так как критерием окончания перемещения влево является достижение элемента, который не больше перемещаемого элемента или достижение самого первого элемента (2 условия), то для упрощения анализа используется принцип барьера. Слева к массиву добавляется еще один элемент, в который помещается значение перемещаемого. Теперь окончание процесса перемещения будет определяться одним условием. Сортировка методом пузырьков. Число проходов по массиву равняется число элементов массива n минус 1. При первом проходе находится максимальный элемент и меняется местами с последним элементом массива. Второй проход идет уже по n-1 элементам массива, за исключением последнего. Находится максимальный элемент среди них и меняется местами с предпоследним элементом массива. И так далее. Вариацией этого метода является сортировка с нахождением минимальных элементов. При первом проходе находится минимальный элемент и меняется местами с первым элементом массива. Второй проход идет, начиная со второго элемента массива. Ищется среди них минимальный элемент и меняется местами со вторым элементом массива. При последнем проходе сравниваются предпоследний и последний элементы массива. Шейкерный метод сортировки является улучшением сортировки методом пузырьков. В нем чередуются проходы вправо с нахождением максимального элемента и проходы влево с нахождением минимального элемента. Существуют еще масса методов сортировки, например, сортировка методом деления пополам, сортировка методом Шелла, древовидная сортировка, быстрая сортировка, которые мы не будем рассматривать.
Следует отличать сортировку массивов от сортировки последовательностей (файлов). Сортировка массивов и сортировка файлов имеют немного общего исходя из их природы. Массивы хранятся в быстрой памяти, в то время как файлы находятся на более медленных внешних накопителях. Одним из методов сортировки последовательностей является сортировка методом слияния. Последовательность разбивается на две половины, каждая из которых сортируется независимо. Две отсортированные подпоследовательности объединяются и затем вновь разбиваются на две половины, которые снова сортируются независимо друг от друга. И так далее, пока не будет отсортирована вся последовательность.