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

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

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

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

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

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

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

1. Что понимается под обработкой информационных массивов?

2. Дайте определение массива. Приведите примеры.

3. Дайте определение файлу, записи, полю, ключу.

4. Чем отличается файл от списка?

5. Что такое упорядочение информационного массива?

6. Чем отличается внутренняя и внешняя сортировка?

7. Каковы критерии качества процесса внутренней сортировки массива?

8. Каковы требования к идеальному алгоритму внутренней сортировки?

9. Какие алгоритмы внутренней сортировки вам известны?

10. Что такое отношение порядка?

11. Чем определяется устойчивость сортировки? Проанализируйте с этой точки зрения метод пузырька.

2.2. Лабораторная работа № 2. Сортировка информационных массивов методом подсчета.

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

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

Этот метод основан на том, что 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. Провести сортировку заданного массива на ЭВМ.