- •1.Введение
- •2.Архитектура машинной памяти
- •3.Адресация основной памяти
- •4.Три уровня представления данных.
- •5.Внутренняя структура записи
- •6.Операции над структурами данных и типы структур данных.
- •7.Последовательное представление данных в памяти эвм.
- •8.Связанное представление данных в памяти эвм.
- •9.Способ хранения, основанный на преобразовании ключа записи в ее адрес.
- •10.Массивы
- •11.Стек.
- •12.Очередь.
- •13.Таблица
- •14.Основные понятия сортировки.
- •15.Основные принципы сортировки
- •16.Сортировка методом выбора
- •17.Сортировка методом обмена (метод пузырька)
- •18.Сортировка методом вставок
- •19.Сортировка методом подсчета (в отсутствии и при наличии одинаковых ключей)
- •20.Сортировка методом Шелла
- •21.Внешняя сортировка.
- •22. Основные принципы информационного поиска
- •23.Последовательный поиск
- •24.Ускоренный последовательный поиск
- •25.Двоичный поиск
- •26.Блочный поиск
- •27.Поиск по двоичному дереву
18.Сортировка методом вставок
При использовании этого метода сортировки упорядоченная последовательность создается на свободном участке памяти. Под сортировку выделяется объем памяти, равный длине отсортированного массива записей. Так как исходная и упорядоченная последовательности располагаются в разных участках памяти, используем для их обозначения различные символы. Элементы исходной последовательности обозначим Аi, а элементы упорядоченной последовательности Bj.
Первый элемент А1 исходной последовательности А занимает первую позицию в свободном участке памяти, т.е. становится первым элементом В1 последовательности В. Элемент А2 сравнивается с В1. Если в результате сравнения оказалось, что А2˂В1, то элемент В1 передвигается на одну позицию, а элемент А2 занимает его прежнее место. Теперь в свободном участке памяти размещены два элемента В1 и В2, образующие последовательность, упорядоченную по возрастанию значений ключа.
В течение каждого i-ого прохода процесса сортировки элемент Аi сравнивается поочередно со всеми элементами последовательности В начиная с В1. При обнаружении Bj , большего Аi, элементы Bj, Bj+1, Bj+2,…, Bj-i передвигаются на одну позицию, освобождая место для элемента Аi, который занимает j-ю позицию.
Последовательность из элементов будет отсортирована за проходов. В первом проходе сравнений не требуется, так как первый элемент просто размещается в первой ячейке памяти. В дальнейшем в течение каждого i-ого прохода будет выполнено i-1 сравнение. Худшим окажется тот случай, когда исходная последовательность уже отсортирована в нужном порядке.
Максимальное число сравнений равно сумме арифметической прогрессии 1+2+3+…+( ) и определяется формулой
Если исходная последовательность имеет обратную упорядоченность, то для сортировки потребуется минимальное число сравнений
Среденее число сравнений пропорционально
Минимальное
число перестановок равно нулю, и будет
это в том случае, когда исходная
последовательность уже упорядочена.
Максимальное число перестановок
потребуется для сортировки исходной
последовательности, имеющей обратную
упорядоченность. Среднее число
перестановок
.
Пример
15 12 8 4 7
12 15 8 4 7
8 12 15 4 7
4 8 12 15 7
4 7 8 12 15
19.Сортировка методом подсчета (в отсутствии и при наличии одинаковых ключей)
Упорядоченная последовательность В создается в свободной области памяти в результате сортировки исходной последовательности А. Метод основан на том, что (К+1)-й элемент упорядоченной последовательности превышает ровно К элементов и, следовательно, занимает (К+1)-ю позицию В процессе сортировки на каждом i-ом проходе i-ый элемент исходной последовательности попарно сравнивается со всеми остальными элементами. Если в результате сравнения установлено, что Аi˃Aj, то згачение числа К увеличивается на единицу. По окончании прохода значение К оказывается равным числу элементов, меньших чем Aj. Номер позиции i-ого элемента в последовательности В равен К+1.
Для сортировки последовательности из N элементов требуется N проходов, на каждом проходе выполняется N сравнений. Число проходов т сравнений не зависят от степени упорядоченности исходной последовательности. Поэтому для данного метода максимальное, минимальное и среднее число сравнений равно N2.
Рассмотренный алгоритм сортировки методом подсчета можно использовать лишь в тех случаях, когда в исходной последовательности отсутствуют одинаковые элементы, иными словами, когда в упорядочиваемом массивк нет записей с одинаковыми значениями ключей. Для сортировки массивов, имеющих записи с одинаковыми значениями ключей, алгоритм нужно модифицировать. Алгоритм состоит из двух просмотров. При первом просмотре для каждого из значений u , u +1,…, v вычисляется количество ключей, равных этому значению. При втором просмотре вычисляются позиции записей, содержащих эти ключи.
ПРИМЕР
