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

Занятие 12

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

Сортировка элементов массива

Метод простого выбора

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

Сортировка Шейкером

Упражнения

Сортировка элементов массива

Под сортировкой понимают процесс перестановки объектов данного массива в определенном порядке. Целью сортировки является упорядочение массивов для облегчения последующего поиска элементов в данном массиве. Существует много методов сортировки массивов.

Метод простого выбора

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

Рассмотрим алгоритмическое решение задачи на примере сортировки некоторого массива значений по возрастанию. В соответствии с вышеописанным методом нам необходимо несколько раз выполнять операции поиска минимального элемента и его перестановку с другим элементом, то есть потребуется несколько раз просматривать элементы массива с этой целью. Количество просмотров элементов массива равно n -1, где n – количество элементов массива.

Рассмотрим выполнение сортировки данным методом на конкретном примере. Пусть исходный массив содержит 5 элементов (2, 8, 1, 3, 7). Количество просмотров согласно модифицированному методу простого выбора будет равно 4. Покажем в таблице 1, как будет изменяться исходный массив на каждом просмотре. Обозначим через k – счетчик (номер) просмотров элементов массива. Отметим, что для перестановки элементов местами необходимо знать их порядковые номера.

Таблица 1. Пример сортировки

Программную реализацию сортировки массива смотрите в упражнении 1.

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

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