- •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 Бинарный поиск
Порядок выполнения работы.
Ознакомится с описанием лабораторной работы №4. Изучить алгоритм сортировки методом Шелла.
Изучить блок-схему данной сортировки.
Написать последовательность сортировки заданного массива методом Шелла в виде таблицы с указанием номеров просмотров (см. пример сортировки).
Произвести подсчет числа сравнений и количества пересылок, полученных при сортировке вашего варианта массива методом Шелла. Сравните полученные данные при сортировке этим методом с данными, полученными в лабораторных работах №1-3 проанализируйте все рассмотренные в лабораторных работах методы сортировок по эффективности на основе ваших данных.
Провести сортировку заданного массива на ЭВМ.
Содержание отчета.
Краткое изложение рассматриваемого метода сортировки, целей и задач лабораторной работы.
Блок-схема алгоритма рассмотренной сортировки.
Таблица последовательности сортировки заданного массива чисел.
Анализ эффективности алгоритма Шелла. Сравнительный анализ с теоретическими данными и с ранее рассмотренными методами сортировок.
Результаты сортировки на ЭВМ (листинг с комментариями).
Контрольные вопросы.
Является ли алгоритм Шелла алгоритмом устойчивой сортировки? Рассмотрите это на примере.
Что такое h-сортировка?
Какие имеются требования к выбору последовательности шагов при сортировке по методу Шелла?
Какова эффективность алгоритма Шелла?
В чем заключается основная идея метода Шелла?
2.5. Лабораторная работа № 5. Последовательный поиск в информационном массиве.
Цель работы: изучение метода последовательного поиска.
Методические указания.
Последовательный поиск записей предполагает существование между элементами ИМ отношения следования. При поиске происходит просмотр записей в соответствии с алгоритмом. Для последовательного поиска в массиве К={K1,K2, … ,Kn} имеется указатель массива I , 1 I n. Над указателем выполняются операции первоначального присвоения ему значения, увеличения или уменьшения.
Алгоритм последовательного поиска заключается в последовательном вводе N элементов массива и проверке значений их ключей на равенство аргументу поиска z. Элемент массива, для которого это равенство выполняется, является искомым. Соответствующее значение указателя i выводится на печать.
Если ни один элемент массива не имеет значения ключа, равного заданному аргументу поиска то выводится сообщение, что элемент не найден.
В данной работе в качестве ИМ используется последовательность целых чисел, разрядность которых с учетом знакового разряда не должна превышать 5, а количество элементов массива не должно превышать 50. Ключом элемента является само число. Для удачного поиска необходимо, чтобы значение аргумента поиска было равно значению какого-либо элемента из заданного массива чисел.
Приведем пример последовательного поиска в массиве из 6 чисел, проделанного вручную.
Дано: К={-50; 2; 7; 559; -37;10001}, z =7.
I=1 К(1)= -50 -507
I=2 К(2)=2 27
I=3 К(3)= 7 7=7
Номер искомого элемента равен 3.
I=4 К(4)=-559 5597
I=5 К(5)= -37 -377
I=6 К(6)=10001 100017
Поиск окончен. Из заданного массива лишь элемент с номером 3 соответствует заданному аргументу поиска.
В исходном элементе может быть несколько элементов, ключи которых совпадают с заданным аргументом поиска z. В этом случае данные ключи можно рассматривать как вторичные. При этом для нахождения всех элементов, соответствующих заданному аргументу поиска, необходимо выполнить n сравнений.
Если выбирать лишь первый встретившийся элемент, удовлетворяющий заданному аргументу поиска, то минимальное количество сравнений будет равно I, а максимальное n.
Среднее количество сравнений при одинаковой частоте использования элементов .
Если имеются статические данные о частоте использования элементов, то среднее количество сравнений , где di – частота использования i-той записи.
Если с каждым элементом ИМ связать счетчик числа обращений к нему, то в процессе функционирования эту статическую информацию можно использовать для реорганизации файла. Это приведет к существенному увеличению быстродействия, но потребует дополнительного объема памяти для организации программных структур счетчиков, а также для организации пересылок.
Использования дополнительной информации можно легко избежать, применяя схему “самоорганизующегося файла”. Она позволяет довольно хорошо упорядочить записи без вспомогательных полей для счетчиков путем нахождения нужной записи и перемещения ее в начало файла. Таким образом, часто используемые элементы будут располагаться в начале ИМ.
Блок-схема последовательного поиска представлена в Приложении 6.