Методы сортировки и поиска в таблице по заданному ключу

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ, МОЛОДЕЖИ И СПОРТА УКРАИНЫ

Донецкий  национальный технический университет 

                                                                  Кафедра СИИ 
 
 
 
 
 
 

Лабораторная  работа №1

по дисциплине «Модели и структуры данных»

на тему: «Методы сортировки и поиска в  таблице по заданному ключу» 
 
 
 
 

Проверили:

_________ ст. пр. Бычкова Е.В.

(дата, подпись)

_________ ас. Мирошниченко А.М.

(дата, подпись)

Выполнил:

_______ ст. гр. СИИ-10а Цветошенко С.В.

(дата, подпись) 
 
 

Донецк

2011

Лабораторная  работа №1

Вариант №23

      Задание к работе:

1. Выбор предметной области.
2. Формирование данных таблицы.
3. Сортировка таблицы. Экспериментальные данные по методам должны быть получены из исходных, которые представлены в трех видах:
• произвольный порядок;
• упорядоченные данные;
• упорядоченные в обратном порядке данные.
4. Провести сравнительный анализ. Теоретические и экспериментальные данные и результаты сравнения различных методов представить в идее таблицы.

       В данном варианте необходимо реализовать  методы поиска по совпадению ключа при наличии нескольких элементов с одинаковым значением ключа, и сортировки методом сравнительного линейного выбора с подсчетом и квадратичной выборки. В качестве полей были выбраны: «Название предприятия», «Город», «Тип», «Количество рабочих» (ключевое поле).

 
 
 

       Теоретические сведения по методам сортировки.

       Линейный  выбор с подсчетом

       При упорядочении таблицы этим методом  необходима память для хранения исходной и упорядоченной таблиц, а также дополнительно должна быть выделена память под счетчик для каждой записи таблицы.

         Просмотр таблицы начинается с первой записи. Ее ключ сравнивается с ключами последующих записей. При этом счетчик большего из сравниваемых ключей увеличивается на 1. При втором просмотре таблицы первый ключ уже не рассматривается, второй ключ сравнивается со всеми последующими. Результаты сравнений фиксируются в счетчиках. Для таблицы, содержащей n элементов, этот процесс повторяется n-1 раз.

         После выполнения всех просмотров  счетчик каждого элемента указывает,  какое количество ключей таблицы  меньше ключа этого элемента. Эти счетчики используются затем в качестве индексов элементов результирующей таблицы. Поместив записи в результирующую таблицу в соответствии со значениями их счетчиков ,получим упорядоченную таблицу. Выполняется n-1 просмотров с n/2 сравнениями в среднем при каждом просмотре. Значения счетчиков изменяются столько раз, сколько выполняется сравнений.

         Число пересылок равно n. 

       Метод квадратичной выборки

       Данный  метод по сравнению с сортировкой  выборкой уменьшает число сравнений, но требует дополнительного объема памяти. Сортируемая таблица, состоящая из n элементов, разделяется на n групп по sqrt(n) элементов в каждой. Если n не является точным квадратом, то таблица разделяется на n' групп, где n' есть ближайший точный квадрат, больший n. В каждой группе выбирается наименьший элемент, который пересылается во вспомогательный список. Вспомогательный список просматривается, и наименьший его элемент пересылается в зону вывода (в зоне вывода формируется отсортированный список). Далее из группы, содержащей элемент, посылаемый в зону вывода, выбирается новый наименьший элемент, который помещается во вспомогательный список. Затем другой просмотр вспомогательного списка выбырает новый наименьший элемент, который является вторым по величине во всем списке. Он пересылается в зону вывода. Элементы групп, которые уже посланы во вспомогательный список, заменяются большими фиктивными величинами.

       Таким образом, при сортировке квадратичной выборкой попеременно просматриваются  то вспоиогательный список, то группа, до тех пор, пока все группы не будут исчерпаны. Такое состояние наступает, когда все группы посылают во вспомогательный список фиктивные величины. Модификацией данного метода является квадратичная выборка с предварительной сортировкой. В этом методе группы сначала полностью упорядочиваются, а затем уже выполняются сравнения между группами.

         Общее число сравнений для  случая точного квадрата равно  приблизительно 2n*sqrt(n), необходимый резерв памяти - поле длиной (n+sqrt(n)) элемент.

       Поиск по совпадению ключа  при наличии нескольких элементов с одинаковым значением ключа (линейный поиск).

       При использовании поиска по совпадению ключа следуют следующему алгоритму: вводится некоторое значение (ключ), далее сравнивается со всеми элементами таблицы и, в случае обнаружения совпадения, цикл прекращается и выводится номер элемента равного заданному ключу. В случае если таких элементов несколько – цикл работает только до первого совпадения. 
 

       Бинарный (двоичный) поиск

       Двоичный  поиск значения в списке (или массиве) используется для упорядоченных  последовательностей (отсортированных  по возрастанию или убыванию). Заключается  такой поиск в определении, содержит ли массив определенное значение, а также определение места его нахождения.

       Описание  алгоритма

       Находится средний элемент последовательности. Для этого первый и последний  элементы связываются с переменными, а средний вычисляется.Средний  элемент сравнивается с искомым  значение. В зависимости от того, больше оно или меньше среднего элемента, дальнейший поиск будет происходить лишь в левой или правой половинах массива. Если значение среднего элемента окажется равным искомому, то поиск завершен.Одна из границ исследуемой последовательности становится равной предыдущему или последующему среднему элементу из п.2.Снова находится средний элемент, теперь уже в «выбранной» половине. Описанный выше алгоритм повторяется уже для данной последовательности. 

       Ручная  трассировка алгоритма линейного  выбора с подсчетом.

       Исходные  числа

       Счетчики

 

Выходной  массив

 

       Ручная трассировка алгоритма методом квадратичной выборки.

 

Зона  накопления

С=3

С=12

Выходной  массив

 
 
 

Ручная  трассировка алгоритма метода линейного поиска. 

Ключ N=16; M- кол-во одинаковых элементов

8 7 16 3 16 9 10 12 23 5 
16!=8;   M=0;

8 7 16 3 16 9 10 12 23 5 
16!=7;   M=0;

8 7 16 3 16 9 10 12 23 5 
16==16;  M=1;

8 7 16 3 16 9 10 12 23 5 
16!=3;   M=1; 

8 7 16 3 16 9 10 12 23 5 
16==16;  M=2;

8 7 16 3 16 9 10 12 23 5 
16!=9;   M=2;

8 7 16 3 16 9 10 12 23 5 
16!=10;  M=2;

8 7 16 3 16 9 10 12 23 5 
16!= 12;  M=2;

8 7 16 3 16 9 10 12 23 5 
16!=23;  M=2;

8 7 16 3 16 9 10 12 23 5 
16!=5;   M=2; 

Ручная  трассировка алгоритма метода бинарного поиска.

Ключ N=4; h – означает средний элемент; M – количество одинаковых значений ключа. Жирным шрифтом обозначены элементы, с которыми сравнивается N.

3 4 4 7 8 9 10 12 16 23 
h1=10/2=5;

3 4 4 7 8 || 9 10 12 16 23 
N<8; M=0;

3 4 4 7 8 || 9 10 12 16 23 
h2=5/2=3;

3 4 4 7 8 || 9 10 12 16 23 
N==4; M=1;

3 4 4 || 7 8 || 9 10 12 16 23 
h3=2/2=1;

3 4 4 || 7 8 || 9 10 12 16 23 
N==4; M=2;

3 4 4 || 7 8 || 9 10 12 16 23

N>3; M=2; 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Алгоритм  работы метода линейного выбора с  подсчетом 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Алгоритм  работы метода линейного поиска