Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
nie.docx
Скачиваний:
3
Добавлен:
24.04.2019
Размер:
425 Кб
Скачать
☆

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 вычисляется количество ключей, равных этому значению. При втором просмотре вычисляются позиции записей, содержащих эти ключи.

ПРИМЕР