Сортировка и поиск

Важнейшими задачами, решаемыми в СУБД при обработке данных, являются задачи сортировки и поиска в таблице.

Сортировкой по заданному ключу является такая перестановка записей (строк), после которой они оказываются упорядоченными в ключевом поле определенным образом. Пример: сортировка записей о студентах по полю «Фамилия» в алфавитном порядке.

Поиск по заданному ключу заключается в отыскании записи (строки), значение ключевого поля которой совпадает с ключом поиска. Пример: поиск записи о студенте по заданной фамилии.

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

Сортировка методом пузырька основана на попарном сравнении смежных элементов данных; если порядок следования элементов в очередной паре неправилен, элементы обмениваются местами. Для обмена используется дополнительная переменная. Время сортировки массива из N элементов пропорционально N².

Сортировка Шелла требует выполнения Nlog₂N операций, где N – число сортируемых элементов. Она похожа на метод пузырька, но начинает сравнивать не смежные, а далеко стоящие друг от друга значения (примерно на N/2). Сортируются все пары, а потом расстояние уменьшается вдвое, сортировка повторяется и т.д. При большом числе элементов сортировка Шелла дает значительный выигрыш во времени.

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

Бинарный (дихотомический) поиск используется для поиска элемента в упорядоченном множестве. Он заключается в последовательном делении множества на две равные части («бинарный» значит «двоичный»). Первоначально областью поиска считается все множество; из него извлекается средний элемент, ключ которого сравнивается с аргументом поиска. Если они совпали, то поиск завершен, в противном случае аргумент может быть больше или меньше ключа среднего элемента. Тогда в зависимости от способа упорядочения данных в качестве области поиска выбирается первая или вторая половина множества, из него извлекается средний элемент и его ключ сравнивается с аргументом поиска. Этот процесс продолжается до тех пор, пока не приведет к успеху или неудаче. Число сравнений при поиске этим способом в среднем пропорционально log₂N, где N – число значений в массиве.