Сортировка информационных массивов методом подсчета.

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

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

Этот метод основан на том, что j-ый ключ в окончательно упорядоченной последовательности превышает ровно (j-1) из остальных ключей. Идея состоит в том, чтобы сравнить попарно все ключи и подсчитать, сколько из них меньше каждого отдельного ключа.

Очевидный способ выполнить сравнение: сравнить K_j c K_i при 1 £ j £ N и при 1 £ i £ N, но легко видеть, что более половины этих действий излишне, поскольку не нужно сравнивать ключ сам с собой и после сравнения K_a c K_b уже не надо сравнивать K_b с К_a. Поэтому достаточно сравнить K_j c K_i при 1 £ j £ i и при 1 £ i £ N.

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

Исходный массив                                    23   4     49   8     12   5     Начальные значения счетчиков Ch(i)     0     0     0     0     0     0     Значения счетчиков после 1-го цикла       1     0     1     1     1     1

Значения счетчиков после 2-го цикла   2     0     2     1     3         

Значения счетчиков после 3-го цикла   3     0     3     2                     

Значения счетчиков после 4-го цикла   3     0     5         

Значения счетчиков после 5-го цикла   4     0         

Результат:                                                              4     0     5     2     3     1

Заметим, что в этом алгоритме записи не перемещаются, а создается массив Ch(i), определяющий конечное расположение записей.

Блок-схема внутренней сортировки методом подсчета представлена в Приложении 2.

Порядок выполнения работы.

1. Ознакомится с общими методическими указаниями и с описанием лабораторной работы.

2. Изучить блок-схему сортировки методом подсчета.

3. Написать последовательность упорядочения заданного массива методом подсчета (см. пример сортировки).

4. Провести сортировку заданного массива на ЭВМ.

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

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

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

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

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

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

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

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

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

Лабораторная работа № 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)

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

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

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

      (2.7)

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

                                 (2.8)

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

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

                                                     (2.9)

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

                        (2.10)

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

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

Порядок выполнения работы.

1. Ознакомится с описанием лабораторной работы №3. Изучить алгоритм сортировки методом вставки и познакомиться по литературе с алгоритмами, использующими метод вставки.

2. Изучить блок-схему сортировки методом вставки.

3. Написать последовательность упорядочения заданного массива методом вставки (см. пример сортировки).

4. Произвести подсчет числа сравнений и количества пересылок, полученных при сортировке вашего варианта массива методом вставки. Сравните полученные данные при сортировке этим методом с сортировками методом пузырька (лабораторная работа №1) по эффективности.

5. Дать сравнительный анализ результатов сортировки вручную с теоретическими результатами расчетов, которые необходимо провести.

6. Провести сортировку заданного массива на ЭВМ.

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

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

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

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

4. Анализ эффективности алгоритма метода вставок с подсчетом числа сравнений и количества пересылок при ручной сортировке.

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

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

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

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

2. Сравните сложность программы для методов пузырька и вставок.

3. Требуется ли при использовании метода вставок резерв памяти?

4. Что такое число инверсий?

5. Зависит ли число сравнений и пересылок от исходного массива чисел?

6. Для чего необходима сортировка?

7. Что такое “бинарные вставки” и “двухпутевые вставки”?

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