Сортировка методом прямого включения
Сортировка методом прямого включения работает со списком неупорядоченных положительных целых чисел ( обычно называемых ключами ), сортируя их в порядке возрастания . Это делается примерно так же , как большинство игроков упорядочивают сданные им карты , поднимая каждый раз по одной карте. Покажем работу общей процедуры на примере следующего неотсортированного списка из восьми целых чисел:
27 412 71 81 59 14 273 87.
Отсортированный список создается заново ; вначале он пуст . На каждой итерации первое число неотсортированного списка удаляется из него и помещается на соответствующее ему место в отсортированном списке. Для этого отсортированный список просматривается , начиная с наименьшего числа , до тех пор, пока не находят соответствующее место для нового числа , т.е. пока все отсортированные числа с меньшими значениями не окажутся впереди него, а все числа с большими значениями --- после него. Следующая последовательность списков показывает ,как это делается:
Итерация 0 Неотсортированный 412 71 81 59 14 273 87
Отсортированный 27
Итерация 1 Неотсортированный 412 71 81 59 14 273 87
Отсортированный 27 412
Итерация 2 Неотсортированный 71 81 59 14 273 87
Отсортированный 27 71 412
Итерация 3 Неотсортированный 81 59 14 273 87
Отсортированный 27 71 81 412
Итерация 4 Неотсортированный 59 14 273 87
Отсортированный 27 59 71 81 412
Итерация 5 Неотсортированный 14 273 87
Отсортированный 14 27 59 71 81 412
Итерация 6 Неотсортированный 273 87
Отсортированный 14 27 59 71 81 273 412
Итерация 7 Неотсортированный 87
Отсортированный 14 27 59 71 81 87 273 412
В следующем алгоритме заводится только один список, и переорганизация чисел производится в старом списке.
Algorithm SIS( Сортировка Прямым включением). Отсортировать на старом месте последовательность целых чисел I(1), I(2), . . . ,I (N) в порядке возрастания.
Шаг 1. [ Основная итерация ]
For J←2 toNdo throughшаг 4 od ;andSTOP.
Шаг 2.[ Выбор следующего целого ] SetK← I(J); and L←J−1.
Шаг 3. [ Сравнение с отсортированного целыми ] WhileK<I(L)
AND L≥1 do setI (L+1)←I(L); andL←L−1 od.
Шаг 4. [ Включение ] SetI(L+1)←K.
QUICKSORT:Алгоритм сортировки со средним временем работы О(N ln N)
Основная причина медленной работы алгоритма SIS заключается в том, что, все сравнения и обмены между ключами в последовательности а1, а2, . . . ,аN происходят для пар из соседних элементов. При таком способе требуется относительно большое
I J
↓ ↓
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Строк 38 08 16 06 79 76 57 24 56 02 58 48 04 70 45 47Действие
1 38 47 уменьшение j
2 38 45
3 38 70
4 38 04 >
5 04 38 обмен
6 08 38 увеличение i
7 16 38
8 06 38
9 79 38 >
10 38 79 обмен
11 38 48
12 38 58
13 38 02 >
14 02 38 обмен
15 76 38 увеличение i,>
16 38 76 обмен
17 38 56 уменьшение j
18 38 24 >
19 24 38 обмен
20 57 38 увеличение i,>
21 38 57 обмен,уменьшение
22 04 08 16 06 02 24 38 57 56 76 58 48 79 70 45 47
( 1 2 3 4 5 6) 7 (8 9 10 11 12 13 14 15 16)
|
время, чтобы поставить ключ, находящийся не на месте , в нужную позицию в сортируемой последовательности. Естественно попытаться ускорить этот процесс , сравнивая пары элементов , находящихся далеко друг от друга в последовательности.
К .Хоор изобрел и весьма эффективно применил эту идею ( алгоритм QUICKSORT), сократив среднее время работы алгоритма SIS от порядка О(N2) до порядка О( N ln N). Поясним этот алгоритм следующим примером.
Предположим , что мы хотим отсортировать последовательность чисел из первой строки на рис. 15. Начнем с предположения , что первый ключ в этой последовательности(38) служит хорошей аппроксимацией ключа , который в конечном счете появится в середине отсортированной последовательности. Используем это значение в качестве ведущего элемента , относительно которого ключи могут меняться местами , и продолжим следующим образом. Устанавливаем два указателя I и J , из которых I начинает отсчет слева (I=1) ,а J- слева в последовательности (J=N). Сравнивая аI и аJ. Если аI≤aJ , устанавливаем J←J−1 и проводим следующее сравнение. Продолжаем уменьшатьJ до тех пор, пока не достигнем аI>аJ. Тогда поменяем местами аI↔aJ (Рис.15 , строка 5 , обмен ключей 38 и 04 ), устанавливаем I←I+1 и продолжаем увеличивать I до тех пор , пока не получим аI>аJ. После следующего обмена ( строка 10, 79↔38) снова уменьшаем J. Чередуя уменьшение J и увеличение I , продолжаем этот процесс с обоих концов последовательности к «середине» до тех пор, пока не получим I=J.
Теперь имеют место два факта. Во-первых,ключ(38),который сначала находился в первой позиции , к этому времени занимает надлежащее место в сортируемой последовательности . Во- первых,все ключи слева от этого элемента будут меньшими, а все ключи справа- большими .
Ту же процедуру можно применить к левой и правой подпоследовательностям для окончательной сортировки всей последовательности. Последняя строка ( с номером 22) рис .15 показывает, что когда будет получено I=J, то I=7. После этого процедура снова применяется к подпоследовательностям (1,6) и (8,16).
Рекурсивный характер алгоритма наводит на мысль , что следует значения индексов крайних элементов большей из двух неотсортированных подпоследовательностей (8,16) поместить на стек и затем перейти к сортировке меньшей подпоследовательности (1,6).
В строке 4 на рис .15 число 04 перешло в позицию 2 и сортировке подлежат подпоследовательности (1,1) и (3,6). Так как (1,1) уже отсортирована (число 02), сортируем (3,6), что в свою очередь ведет к строке 6 , в которой подлежат сортировке (3,4) и (6,6). В строке 7 подпоследовательность (1,6) отсортирована. Теперь извлекаем (8,16) из стека и начинаем сортировку этой подпоследовательности. В строке 13 находятся подпоследовательности (8,11) и (13,16), которые надо отсортировать. Помещаем (13,16) на стек, сортируем (8,11) и т.д. В строке 20 последовательность целиком отсортирована.
Прежде чем описать алгоритм QUICKSORT формально, нужно точно показать ,как он работает. Мы пользуемся стеком [ LEFT (K), RIGHT (K) ] для запоминания индексов крайних левого и правого элементов еще не не отсортированных подпоследовательностей. Так как короткие подпоследовательности быстрее сортируются при помощи обычного алгоритма , алгоритм QUICKSORT имеет входной параметр М, который определяет, насколько короткой должна бать подпоследовательность, чтобы ее сортировать обычным способом.Для этой цели пользуемся сортировкой простыми включениями (SIS).
Поиск
Теперь обратимся к исследованию некоторых основных проблем , относящихся к поиску информации на стуктурах данных. Как и в предыдущем разделе, посвященному сортировки, будем предполагать , что вся информация хранится в записях , которые можно идентифицировать значениями ключей , т.е. записи Ri соответствует значение ключа ,обозначаемое Ki.
Предположим ,что в файле расположены случайным образом N записей в виде линейного массива. Очевидным методом поиска заданной записи будет последовательный просмотр ключей. Если найден нужный ключ, поиск оканчивается успешно; в противном случае будут просмотрены все ключи , а поиск окажется безуспешным .Если все возможные порядки расположения ключей равновероятны , то такой алгоритм требует O(N) основных операций как в худшем, так и в среднем случаях. Время поиска можно заметно уменьшить , если предварительно упорядочить файл по ключам. Эта предварительная работа имеет смысл , если файл достаточно велик и к нему обращаются часто.
Далее будем предполагать, что у нас есть N записей , уже упорядоченных по ключам так , что К1<К2<…<КN. Пусть дан ключ К и нужно найти соответствующую запись в файле (безуспешный поиск ).
Предположим, что мы обратились к середине файла и обнаружили там ключ Ki. Сравним К и Кi. Если К=Кi, то нужная запись найдена . Если К<Кi ,то ключ К должен находиться в части файла, предшествующей Кi ( если запись с ключом К вообще существует) . Аналогично, если Кi<К, то дальнейший поиск следует вести в части файла, следующей за Кi. Если повторять эту процедуру проверки ключа Кi из середины непросмотренной части файла , тогда каждое безуспешное сравнение К с Кi будет исключать из рассмотрения приблизительно половину непросмотренной части.
Блок-схема этой процедуры , известной под названием двоичный поиск, приведена на рис.16
AlgorithmBSEARCH (Binary search- двоичный поиск) поиска записи с ключом К в файле с N≥2 записями , ключи которых упорядочены по возрастанию К1<К2…<КN.
Шаг 0.[Инициализация] SetFIRST←1 ; LAST← N. (FIRST и LAST- указатели первого и последнего ключей в еще не просмотренной части файла.)
Шаг 1.[Основной цикл ] WhileLAST≥FIRST do throughшаг 4 od.
Шаг 2. [Получение центрального ключа] SetI←|_(FIRST + LAST)/2_| .(Кi- ключ, расположенный в середине или слева от середины еще не просмотренной части файла.)
Шаг 3.[Проверка на успешное завершение ] If К=КI thenPRINT «Успешное окончание, ключ равен КI»;andSTOP fi.
Шаг 4. [ Сравнение] IfK<KI then setLAST←I-1 else setFIRST←I+1 fi.
Шаг 5. [ Безуспешный поиск] PRINT «безуспешно»; andSTOP.
Алгоритм BSEARCH используется для отыскания К=42 на рис.17.
Метод двоичного поиска можно также применить для того, чтобы представить упорядоченный файл в виде двоичного дерева . Значение ключа, найденное при первом выполнении шага 2 (К(8)=53), является корнем дерева. Интервалы ключей слева (1,7) и справа (9,16) от этого значения помещаются на стек. Верхний интервал снимается со стека и с помощью шага 2 в нем отыскивается средний элемент (или элемент слева от середины). Этот ключ (К(4)=33) становится следующим после корня элементом влево , если его значение меньше значения корня , и следующим вправо в противном случае. Подынтервалы этого интервала справа и слева от вновь добавленного ключа [(1,3) , (5,7)] помещаются теперь на стек .Эта процедура повторяется до тех пор , пока стек не окажется пустым. На рис.18 показано двоичное дерево, которое было бы построено для 16 упорядоченных ключей с рис .17.
Двоичный поиск можно теперь интерпретировать как прохождение этого дерева от корня до искомой записи. Если достигнута конечная вершина, а заданный ключ не найден , искомая запись в данном файле отсутствует. Заметим, что число вершин на единственном пути от корня к заданному ключу К равно числу сравнений, выполняемых алгоритмом BSEARCH при попытке отыскания К.
| Да |
