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

Лабораторная работа №4

 

1. Цель и задачи работы

 

Изучение метода сортировки массивов методом включений. Написание программы, демонстрирующей изученные принципы.

 

2. Теоретические сведения

Сортировка методом включений

 

Разделим условно РІСЃРµ записи РЅР° готовую последовательность:

R₁, R₂, …, R_i-1;

и входную (исходную) последовательность:

R_i, R_i+1, …, R_n.

На каждом шаге, начиная с i=2 и увеличивая i на единицу, будем извлекать очередной i-й элемент из входной последовательности, и вставлять его в готовую последовательность, при этом элемент вставляется на нужное место.

В таблице 1 представлен пример процесса сортировки с помощью включений восьми случайно выбранных чисел.

 

Таблица 1. Пример сортировки с помощью включений

№ итерации	Последовательность
Исходный	44	55	12	42	94	18	06	67
2	44	55	12	42	94	18	06	67
3	12	44	55	42	94	18	06	67
4	12	42	44	55	94	18	06	67
5	12	42	44	55	94	18	06	67
6	12	18	42	44	55	94	06	67
7	06	12	18	42	44	55	94	67
8	06	12	18	42	44	55	67	94

 

При поиске подходящего места для текущего элемента удобно чередовать сравнения и движения по последовательности, т.е. текущий элемент сравнивается с очередным элементом R_j, а затем либо текущий элемент вставляется на свободное место, либо R_i сдвигается вправо, и процесс «уходит» влево.

При этом, пересылая текущий элемент с места l на место k, мы заполняем место l элементом с индексом (l-1), а пустое место элемента (l-1) элементом с индексом (l-2), и так далее, до бывшего элемента с индексом k, который становится на место (k+1). Другими словами сдвигаем последовательность вправо.

Данное «просеивание» может закончиться в двух случаях:

1. Найден элемент R_i с ключом, меньшим, чем ключ текущего элемента.

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

Эти два условия окончания цикла дает возможность рассмотрения фиктивного элемента — барьера. Этот элемент может быть не включен в сортировку, что приведет к ошибке алгоритма или к ошибочной сортировке. Для решения этой проблемы достаточно расширить диапазон индексов на одну ячейку в описании элементов R_i.

Алгоритм сортировки простыми включениями легко можно улучшить, пользуясь тем, что готовая последовательность, в которую нужно вставить новый элемент, уже упорядочена. Поэтому место включения можно найти гораздо быстрее. Очевидно, что здесь можно применить бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями.

 

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

 

При сортировке прямыми включениями число сравнений ключей (C_i) при i-м просеивании составляет самое большое (i-1), самое меньшее — 1; если предположить, что все перестановки из N ключей равновероятны, то среднее число сравнений — i/2. Число пересылок (присваиваний элементов) M_i равно (C_i+2) (учитывая барьер). Поэтому общее число сравнений и пересылок можно найти по формулам:

 

C_min= N-1ВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВ M_min=3(N-1)

C_avg=Вј(N²+N-2)ВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВ M_avg=Вј(N²+9N-10)

C_max=Вј(N²+N-4)ВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВ M_max=ВЅ(N²+3N-4)

Наименьшие числа появляются, если элементы с самого начала упорядочены, а наихудший (наибольшее число) случай встречается, если элементы расположены в обратном сортировке порядке. Заметим, что данный алгоритм описывает так называемую устойчивую сортировку, т.е. оставляет неизменным порядок следования элементов с одинаковыми значениями.

РџСЂРё сортировке бинарными включениями РІ конце РїРѕРёСЃРєР° интервал должен быть единичной длины; значит, деление его пополам производится i*log₂(i) раз. Таким образом:

C = [log₂ i].

Количество сравнений не зависит от исходного порядка элементов. Но из-за округления при делении интервала поиска пополам действительное число сравнений для i элементов может быть на 1 больше ожидаемого. Природа этого «перекоса» такова, что в результате места′ включения в нижней части находятся в среднем несколько быстрее, чем в верхней части. Это дает преимущество в тех случаях, когда элементы изначально далеки от правильного порядка. На самом же деле минимальное число сравнений требуется, если элементы вначале расположены в обратном порядке, а максимальное — если они уже упорядочены. Следовательно, это случай неестественного поведения алгоритма сортировки:

C = N (log₂N – log₂e В± 0,5).

Рљ сожалению, улучшение, которое РјС‹ получаем, используя метод бинарного РїРѕРёСЃРєР°, касается только числа сравнений, Р° РЅРµ числа необходимых пересылок. Р’ действительности, поскольку пересылка элементов, С‚.Рµ. ключей Рё сопутствующей информации, обычно требует значительно больше времени, чем сравнение РґРІСѓС… ключей, то это улучшение РЅРё РІ коей мере РЅРµ является решающим: важный показатель Рњ (число пересылок элементов) РїРѕ-прежнему остается РїРѕСЂСЏРґРєР° N². И РІ самом деле, пересортировка уже рассортированного массива занимает больше времени, чем РїСЂРё сортировке простыми включениями СЃ последовательным РїРѕРёСЃРєРѕРј! Этот пример показывает, что «очевидное улучшение» часто оказывается намного менее существенным, чем кажется вначале, Рё РІ некоторых случаях может РЅР° самом деле оказаться ухудшением.

 

 

3. Схемы алгоритмов сортировок прямым и бинарным включением

 

На рисунке 1 представлена схема алгоритма сортировки прямым включением, а на рисунке 2 — бинарным включением.

 

РРёСЃ. 1. Схема алгоритма сортировки прямым включением.

 

 

РРёСЃ. 2. Схема алгоритма сортировки бинарным включением.

 

 

4. Варианты заданий

 

1. Отсортировать массив, состоящий РёР· 2ⁿ элементов.

2. Отсортировать натуральные числа (1…9), заданные в произвольном порядке.

3. Отсортировать массив, состоящий из положительных чисел.

4. Отсортировать массив, состоящий из отрицательных чисел.

5. Отсортировать массив, состоящий из положительных двузначных чисел.

6. Произвести сортировку массива, состоящего из 0 и 1, записанных в произвольном порядке.

7. Отсортировать клавиши на клавиатуре в порядке убывания их ASCII–кодов.

8. Отсортировать клавиши на клавиатуре в порядке возрастания их ASCII–кодов.

9. Отсортировать по возрастанию массив, состоящий букв введенных с клавиатуры имени и фамилии, считая что, а=1, б=2, в=3, …я=33.

10. Отсортировать массив, состоящий из (2n+1) элементов. Сортировку до (n+1)-го элемента осуществлять по возрастанию, а после (n+1)-го — по убыванию, т.е. «горкой».

1ВВВ 2ВВВ 3ВВВ 4ВВВ 5ВВВ 4ВВВ 3ВВВ 2ВВВ 1

nВВВ ВВВВВВВ n+1ВВВВ ВВВ n

11. Отсортировать массив, состоящий из (2n+1) элементов «оврагом».

5ВВВ 4ВВВ 3ВВВ 2ВВВ 1ВВВ 2ВВВ 3ВВВ 4ВВВ 5

nВВВ ВВВВВВВ n+1ВВВВ ВВВ n

12. Отсортировать последовательности, состоящие из натуральных чисел 1…9 и 9…1 и сравнить характеристики сортировки в первом и во втором случаях.

13. Провести сортировку массивов, состоящих РёР· 2⁵ Рё 2⁶ чисел Рё сравнить характеристики сортировки.

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

15. Реализовать метод сортировки прямым включением массива строк.

16. Реализовать метод сортировки бинарным включением, сравнить СЃ характеристиками РїСЂСЏРјРѕРіРѕ включения.

17. Реализовать метод сортировки прямым включением для матрицы. Сортировка осуществляется РїРѕ столбцам матрицы.

18. Реализовать метод сортировки бинарным включением для диагоналей матрицы.

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

20. Даны два массива A и B, каждый из которых состоит из n элементов (n=1, 2, 3, ...). Построить третий массив C, таким образом, что c_i=a_i+b_i (i=1,…,n). Отсортировать его по возрастанию методом бинарного включения.

 

5. Указания по составлению отчета

 

Отчет должен содержать:

- название, цель лабораторной работы,

- постановку и описание задачи,

- решение задачи (схемы алгоритмов программ подпрограмм),

- текст составленной программы в среде программирования Delphi,

- тестовый пример,

- инструкцию пользователю,

- инструкцию программисту,

- краткие выводы.

 

 

Библиографический список

 

1. Вирт Н. Алгоритмы + структуры = программы: пер. с англ. М.: Мир, 1985.

2. Вирт Н. Алгоритмы и структуры данных: пер. с англ. М.: Мир, 1989.

3. Кнут Д. Искусство программирования для ЭВМ. Сортировка и поиск. Т.3. М.: Мир, 1977.