13. Алгоритмы поиска, выборки и сортировки. Алгоритм последовательного поиска (АПП) последовательно просматривает по одному элементу списка, начиная с первого, до тех пор, пока не найдет целевой элемент. Предполагается, что список не отсортирован. Наихудший случай: целевой элемент стоит в списке последним или его вовсе нет в списке. Средний случай: поиск всегда завершается успешно, или иногда целевое значение в списке отсутствует. Алгоритм двоичного поиска (АДП): Двоичный поиск осуществляется на отсортированном списке. Идея в том, что список делится пополам, берется средний эл-т и сравнивается с целевым эл-том. При сравнении возможен один из трех результатов: значения равны, целевое значение меньше элемента списка, либо целевое значение больше элемента списка. В первом, и наилучшем, случае поиск завершен. В остальных двух случаях мы можем отбросить половину списка. Когда целевое значение меньше среднего элемента, мы знаем, что если оно имеется в списке, то находится перед этим средним элементом. Когда же оно больше среднего элемента, мы знаем, что если оно имеется в списке, то находится после этого среднего элемента. Этого достаточно, чтобы мы могли одним сравнением отбросить половину списка. При повторении этой процедуры мы сможем отбросить половину оставшейся части списка. В наихудшем случае число проходов равно k = log2(N +1). Средний случай A(N)≈ log2(N +1)-1 Алгоритм выборки Иногда нам нужен эл-т из списка, обладающий некоторыми специальными св-ми, а не имеющий некоторое конкретное значение. Например, в списке сотрудников найти среднего по возрасту или найти 5 сотрудников с наименьшей оплатой труда. В более общем случае нас может интересовать запись с К-ым по величине значением поля. Один из способов найти такую запись состоит в том, чтобы отсортировать список в порядке убывания; тогда запись с К-ым по величине значением окажется на К-ом месте. На это уйдет гораздо больше сил, чем необходимо: значения, меньшие искомого, нас, на самом деле, не интересуют. Может пригодиться следующий подход: мы находим наибольшее значение в списке и помещаем его в конец списка. Затем мы можем найти наибольшее значение в оставшейся части списка, исключая уже найденное. В результате мы получаем второе по величине значение списка, которое можно поместить на второе с конца место в списке. Повторив эту процедуру К раз, мы найдем К-ое по величине значение. Алгоритмы сортировки Сортировка вставками. На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. Приведенный ниже алгоритм использует именно эту стратегию выбора. Вход: массив A, состоящий из элементов A[1], A[2], ..., A[n] for i = 2, 3, ..., n: key := A[i] j := i - 1 while j > 0 and A[j] > key: A[j + 1] := A[j] j := j - 1 A[j + 1] := key Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим — массив, отсортированный в порядке, обратном нужному. Временная сложность алгоритма при худшем варианте входных данных — θ(n²). Пузырьковая сортировка. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма. Сортировка Шелла. При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d = 1 (то есть, обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места. Пример. Пусть дан список A = (32,95,16,82,24,66,35,19,75,54,40,43,93,68) и выполняется его сортировка методом Шелла, а в качестве значений d выбраны 5,3,1. На первом шаге сортируются подсписки A, составленные из всех элементов A, различающихся на 5 позиций, то есть подсписки A5,1 = (32,66,40), A5,2 = (95,35,43), A5,3 = (16,19,93), A5,4 = (82,75,68), A5,5 = (24,54). В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов. Процесс завершается обычной сортировкой вставками получившегося списка.
Корневая сортировка. Общий список разбивается на стопки в соответствии с разрядом ключа. При каждом проходе осуществляются перестановки в соответствии со значением отдельной части ключа. После каждого прохода происходит объединение стопок и их разбиение по другому разряду ключа. Быстрая сортировка. Рекурсивный алгоритм сортировки. Выбрав элемент в списке, быстрая сортировка делит с его помощью список на две части. В одной части элементы больше выбранного, в другой - меньше. Сортировка слиянием. Алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке.
Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным). |