3. Быстрая сортировка Хоара
Быстрая сортировка, как и сортировка слиянием, также является реализацией принципа 'разделяй и властвуй". Элементы сортируемого массива переставляются так. чтобы массив условно разделился на две
части - левую и правую, причём никакой элемент из левой части не должен превосходить никакого элемента из правой.
После этого процедура сортировки вызывается рекурсивно для левой и правой части, в результате чего массив будет отсортирован.
Для получения такого разбиения можно действовать следующим образом. Пусть дан массив а[р..г]. Элемент х=а[р] выбирается в качестве граничного (опорного). Нам нужно добиться, чтобы для некоторого q выполнялось следующие условия:
• элементы a[p..q] не больше х
• элементы a[q-l..r] не меньше х
• p<q<r
Строгое неравенство в последнем условии говорит о том, что после разбиения обе получившиеся части должны быть не пустыми, иначе алгоритм зациклится.
Наихудший случай, когда при каждом разбиении получаются наиболее неравные части - один элемент н оставшиеся. Поскольку одно разбиение выполняется за линейное время, то сортировка выполнится за0(n2).
Среднее время работы алгоритма составляет O(n * log n).
6. Поиск
Задача поиска формулируется так — найти запись (или несколько записей), у которых значение ключа совпадает с заданным значением, которое требуется найти. При этом становится доступной связанная с ключом информация. Обычно получение этой информации и является целью поиска. Иногда поиск может преследовать и более скромную цель— просто убедиться, что запись с искомым значением ключа имеется в совокупности данных.
1. Последовательный (линейный) поиск
Самая простая реализация поиска— использование обычного неупорядоченного массива или связного списка для хранения данных. Однако при небольших размерах совокупности данных (до нескольких тысяч записей) этот метод обеспечивает приемлемую скорость поиска, поэтому находит применение (в БД такой случай называют полным просмотром таблицы).
Алгоритм линейного поиска предельно прост— необходимо просматривать все элементы по порядку (в прямом или обратном направлении) до тех пор. пока не будет найден искомый элемент или массив (список) не будет исчерпан. Данный алгоритм реализуется при помощи цикла, на каждом шаге которого выполняются два сравнения. Если массив уже исчерпан, а искомый элемент так и не найден, это является признаком промаха при поиске.
Следовательно, алгоритм имеет линейную сложность 0(п).
2. Бинарный поиск в упорядоченном массиве
Он состоит в делении упорядоченного массива пополам, при этом мы определяем, в какой из двух половин находится искомый элемент. В упорядоченном массиве это сделать можно, сравнив искомый элемент и тот. который находится в точке деления. Обратим внимание, что размер массива уже сократился) вдвое. Но продолжаем делить нужную половину массива. При этом локализуем уже четверть массива и т. д. Процесс продолжается до конца. когда в массиве останется один последний элемент. Если он совпадает с искомым значением, то поиск успешен, в противном случае имеем промах.
Асимптотическая оценка сложности поиска O(Iog n)