Сортировка методом прямого включения

Необходимые определения и классификация сортировок.

Сортировка. Необходимые определения и классификация сортировок. Сортировки прямого включения и выбора. Их эффективность

Сортировка – это расположение данных в памяти в регулярном виде по их ключам. Так что при обработке данных важно знать информационное поле данных и размещение их в машине. Поэтому различают внутреннюю (сортировка в оперативной памяти) и внешнюю сортировки (сортировка во внешней памяти). Регулярность расположения элементов – это возрастание (убывание) значения ключа от начала к концу в массиве.

Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того чтобы их уменьшить, используют метод сортировки таблицы адресов. Этот метод применяют в таблице адресов ключей. Производят перестановку указателей, т.е. Сам массив не перемещается. При сортировке могут встретиться и одинаковые ключи. В этом случае одинаковые ключи желательно расположить после сортировки в том же порядке, что и в исходном файле. Этот принцип используется для устойчивой сортировки.

Эффективность сортировки можно рассматривать с нескольких критериев:

1) время, затрачиваемое на сортировку;

2) объем оперативной памяти, требуемой для сортировки;

3) время, затраченное программистом на написание программы.

Время, затраченное на сортировку, пропорционально количеству сравнений при выполнении сортировки и количеству перемещений элементов.

Считается, что порядок числа сравнения при сортировке может находиться в пределах от о(nlogn) до о(n²), где о(n) - идеальный и недостижимый случай.

Методы сортировки можно классифицировать примерно так:

1) строгие (прямые) методы (их эффективность примерно одинакова):

· прямого включения;

· прямого выбора;

· прямого обмена;

2) улучшенные методы.

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

Элементы мысленно делятся на уже готовую последовательность a₁,...,a_i-1 и исходную последовательность. В готовой последовательности элементы располагаются в заданном порядке (по убыванию или по возрастанию). А в исходной последовательности располагаются элементы, которые и нужно отсортировать. При каждом шаге элементы исходной последовательности уменьшаются на единицу, а готовая увеличивается на единицу. Это происходит из-за того, что из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место среди элементов готовой последовательности.

Рассмотрим пример сортировки методом прямого включения на последовательности элементов: 10, 3, 11, 8, 2, 15, 44, 9 (табл. 11.1). Необходимо её отсортировать по возрастанию.

Сначала готовая последовательность не имеет элементов. На первом шаге первый элемент исходной последовательности – это 10, становится первым элементом готовой последовательности. Далее второй шаг: элемент 3 из исходной последовательности помещается в готовую. Это происходит так. Если элемент больше 10, то он остаётся на своём месте, а если меньше, то 10 сдвигается на единицу вправо и на её место ставится элемент. Так как 3<10, то готовая последовательность теперь будет иметь вид: 3, 10, а исходная – 11, 8, 2, 15, 44, 9. Далее на третьем шаге из исходной последовательности выбирается 11 и помещается в готовую последовательность. Сначала 11 сравнивается с 10, и так как 11>10, то 11 остаётся на месте. Исходная последовательность теперь равна: 8, 2, 15, 44, 9. Последующие шаги производятся аналогичным образом.

Таблица 11.1

Принцип работы сортировки прямым включением

Число шагов в данной сортировке (табл. 11.1) равно числу элементов в сортируемой последовательности, т.е. 8 шагов = 8 элементов.

Существуют два способа реализации данного метода – это без барьера (рис. 11.1) и с барьером (рис. 11.2).