Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Методические указания. Одно из важнейших семейств методов сортировки основано на использовании следующей идеи: предполагается




Одно из важнейших семейств методов сортировки основано на использовании следующей идеи: предполагается, что перед рассмотрением записи aj предыдущие записи a1, …, aj-1 уже упорядочены, и aj вставляется в соответствующее место. На основе этой схемы возможны несколько вариаций. В лабораторной работе изучается разновидность, которая называется методом простых вставок.

Алгоритм сортировки методом простых вставок заключается в следующем. Пусть и записи a1, …, aj-1 уже размещены так, что . Будем сравнивать по очереди Кj c Кj-1, Кj-2, … до тех пор, пока не обнаружим, что запись aj следует вставить между ai и ai+1; тогда подвинем записи ai+1,…, aj+1 на одно место вправо и поместим новую запись в позицию i+1.

Удобно совмещать операции сравнения и перемещения, перемежая их друг с другом. Поскольку запись aj как бы “проникает на положенный ей уровень”, этот способ называют “просеиванием” или “погружением”.

Приведем пример сортировки массива из 5 чисел:

Исходный массив 5 2 4 1 3

Первое сравнение 5 : 2

2 5 : 4

2 4 5 : 1

1 2 4 5 : 3

Массив упорядочен 1 2 3 4 5

Знак “ : ” означает сравнение. Стрелкой показана пересылка элемента.

Эффективность алгоритма зависит от числа сравнений и пересылок. Грубую оценку среднего числа сравнений можно произвести очень просто. Действительно, когда обрабатывается j-я запись, ее ключ сравнивается в среднем примерно с j/2 ранее отсортированными ключами; поэтому общее число сравнений приблизительно равно

(2.5)

Можно более точно оценить количество сравнений, используя понятие инверсии. Число проверок условий Кi<Kj зависит от числа инверсий в сортируемом множестве. Количество сравнений

(2.6)

где aj – число инверсий (число элементов, больших Кj и стоящих слева от него).

Так число инверсий aj и аj связано с номером следующим соотношением:

Пусть независимы, тогда максимальное количество сравнений определяется формулой

(2.7)

Минимальное количество сравнений определяется формулой

(2.8)

где aj = 0 , т.е. массив упорядочен.

Среднее количество сравнений определяется из предположения, что среднее количество инверсий равно

(2.9)

Тогда среднее количество сравнений задается формулой

(2.10)

Усовершенствованиями метода простых вставок являются методы: бинарных вставок, двухпутевые вставки, метод Шелла, вставки в список и др. Познакомиться с этими методами и их сравнительными оценками можно по литературе.

Блок-схема данного метода представлена в Приложении 3.


mylektsii.ru - Мои Лекции - 2015-2019 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал