Содержание отчета.

1. Краткое изложение задачи внутренней сортировки, рассматриваемого метода сортировки, целей и задач лабораторной работы.

2. Блок-схема алгоритма рассмотренной сортировки.

3. Таблица последовательности сортировки заданного массива чисел с указанием номеров просмотров (сортировка вручную).

4. Результаты сортировки на ЭВМ (листинг с комментариями).

5. Сравнительный анализ (конкретный по полученным данным) метода подсчетом и метода пузырька. Обобщение анализа на большие массивы данных.

Контрольные вопросы.

1. В чем особенность сортировки методом подсчета?

2. Проанализируйте с точки зрения устойчивости метод сортировки подсчетом. Является ли он устойчивым?

2.3. Лабораторная работа № 3. Сортировка информационных массивов методом вставки.

Цель работы: изучение процесса сортировки информационных машинных массивов методом вставки.

Методические указания

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

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

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

Приведем пример сортировки массива из 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<K_j зависит от числа инверсий в сортируемом множестве. Количество сравнений

(2.6)

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

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

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

(2.7)

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

(2.8)

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

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

(2.9)

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

(2.10)

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

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