Сортировка данных

Сортировка данных в хранилище необходима, прежде всего, для реализации поиска. Большинство современных методов поиска базируются на 2-х методах, обменная сортировка и сортировка Шелла.

Алгоритм пузырьковой сортировки.

1. Ключи в первых двух записях. Если первая запись больше второй они меняются местами.

2. Затем сравняются 2-я и 3-я записи, и если их ключи стоят не по порядку меняются местами.

3. Тем же способом последовательно обрабатываются ключи. При этом наибольшее значение ключа переносится в значение N (таблица размерности).

4. Описанные действия повторяются для N-1 позиции таблицы, затем для N-2 до тех пор пока не будит достигнуто начало таблицы.

Достоинства: простота реализации.

Недостаток: большое время сортировки, которое с увеличением количества записей увеличивается и способствует увеличению времени сортировки в гиперболической прогрессии.

Сортировка Шелла

1.

1. Вся последовательность записей условно разбивается пополам и сравнивается 1-й элемент 1 таблицы с 1-м элементом 2-й таблицы, 2-й элемент 1-й таблицы с 2-м элементом 2-й таблицы. Меньшее значение отправляется в начало большее в конец таблицы.

2.

2. Половинки разбиваются на 2 части, и те же действия выполняются для половинок. Алгоритм выполняется до тех пор, пока во фрагментах таблицы не останется по 1-му элементу и не будит произведено сравнение всех пар.

Достоинства: более быстрый алгоритм сортировки.

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

В больших БД с большими объемами информации упорядочивать записи затруднительно вместо этого применяют т.н. хеш кодирование.

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

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

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

Дата добавления: 2013-12-12