- •1. Основные понятия сортировки и поиска.
- •1.1. Сортировка.
- •1.2. Поиск.
- •2.1. Лабораторная работа № 1. Сортировка методом попарной перестановки (“метод пузырька”).
- •Методические указания.
- •Порядок выполнения работы.
- •Массив чисел (ключей)
- •Содержание отчета.
- •Контрольные вопросы.
- •2.2. Лабораторная работа № 2. Сортировка информационных массивов методом подсчета.
- •Методические указания
- •Порядок выполнения работы.
- •Содержание отчета.
- •Контрольные вопросы.
- •2.3. Лабораторная работа № 3. Сортировка информационных массивов методом вставки.
- •Методические указания
- •Порядок выполнения работы.
- •Содержание отчета.
- •Контрольные вопросы.
- •2.4. Лабораторная работа № 4. Сортировка информационных массивов методом Шелла.
- •Методические указания.
- •Порядок выполнения работы.
- •Содержание отчета.
- •Контрольные вопросы.
- •2.5. Лабораторная работа № 5. Последовательный поиск в информационном массиве.
- •Методические указания.
- •Порядок выполнения работы.
- •Содержание отчета.
- •Контрольные вопросы.
- •2.6. Лабораторная работа № 6. Бинарный поиск в информационном массиве.
- •Методические указания.
- •Порядок выполнения работы.
- •Содержание отчета.
- •Контрольные вопросы.
- •3. Литература.
- •Приложение 5 Бинарный поиск
2.1. Лабораторная работа № 1. Сортировка методом попарной перестановки (“метод пузырька”).
Цель работы: изучение процесса сортировки информационных машинных массивов методом попарной перестановки.
Методические указания.
Сортировка данным методом выполняется путем многократного просмотра множества ключей. Мы будем рассматривать числовые ключи, поэтому в дальнейшем будут рассматриваться массивы чисел. При каждом последовательном просмотре массива сравниваются соседние числа (ключи). Если числа в паре расположены в порядке возрастания, оставляем их без изменения; в противном случае меняем их местами. Затем (в любом случае) переходим к следующей паре. Сортировка считается оконченной, если в ходе просмотра не была произведена ни одна перестановка. В результате на первом шаге процесса (после 1-го просмотра) на последнее место в массиве из N чисел ставится самое большое число и при следующем просмотре чисел массива анализируется (N-1) чисел, при третьем просмотре (N-2) чисел и т.д. Таким образом, сокращается время упорядочения.
Этот метод называют иначе “метод пузырька”: большие элементы (записи с большими ключами), подобно пузырькам, “всплывают” на соответствующую позицию.
Приведем пример сортировки массива из 6 чисел:
Исходный массив 1 7 6 4 2 5
6 7 4 7 2 7 5 7
после первого просмотра 1 6 4 2 5 7
4 6
2 6
5 6
после второго просмотра 1 4 2 5 6 7
2 4
после третьего просмотра 1 2 4 5 6 7.
Сортировка окончена, так как во время четвертого просмотра не было совершено ни одной перестановки.
Количество сравнений определяется максимальным количеством инверсий:
(2.1)
где , . Определение инверсий, относящихся к описанию комбинаторных свойств перестановок, можно найти в [1]. Если для (массив упорядочен), то минимальное количество сравнений
(2.2)
Если k=N-1, то формула принимает вид
(2.3)
Среднее количество сравнений может быть подсчитано по формуле, исходя из того, что среднее количество инверсий равно :
(2.4)
Приведенные формулы указывают на возможную оценку количества сравнений при использовании метода пузырька. Блок-схема сортировки представлена в Приложении 1.
Порядок выполнения работы.
Ознакомится с общими методическими указаниями и с описаниями данной лабораторной работы. Ознакомиться по литературе с основными понятиями обработки информационных массивов, алгоритмами внутренней сортировки и требованиями к ним.
Изучить блок-схему сортировки “методом пузырька”.
Каждому студенту получить номер варианта и из таблицы 2.1. выбрать соответствующий неупорядоченный массив из N = 8 чисел. Этот массив чисел используется для сортировки различными методами в лабораторных работах 1-4.
Написать последовательность упорядочения заданного массива методом пузырька (см. пример сортировки).
Произвести подсчет числа сравнений и количества пересылок, необходимых при сортировке вашего варианта массива, и провести сравнение с теоретическими данными. Дать оценку эффективности рассматриваемого алгоритма сортировки.
Провести сортировку заданного массива на ЭВМ.
Таблица 2.1