Сортировка методом прямого включения

Сортировка методом прямого включения работает со списком неупорядоченных положительных целых чисел (обычно называемых ключами), сортируя их в порядке возрастания. Это делается примерно так же, как большинство игроков упорядочивают сданные им карты, поднимая каждый раз по одной карте. Покажем работу общей процедуры на примере следующего неотсортированного списка из восьми целых чисел:

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 to N do through шаг 4 od; and STOP.

Шаг 2. [ Выбор следующего целого ] Set K← I(J); and L←J−1.

Шаг 3. [ Сравнение с отсортированного целыми ] While K<I(L)

AND L≥1 do set I (L+1) ← I(L); and L←L−1 od.

Шаг 4. [ Включение ] Set I(L+1)←K.

 

 

 

QUICKSORT: Алгоритм сортировки со средним временем работы О(N ln N)

Основная причина медленной работы алгоритма SIS заключается в том, что, все сравнения и обмены между ключами в последовательности а₁, а₂,...,а_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)

 

 

	Рис. 15 Начальные шаги алгоритма QUICKSORT при сортировке последовательности целых чисел.

 

 

 

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

 

К.Хоор изобрел и весьма эффективно применил эту идею (алгоритм QUICKSORT), сократив среднее время работы алгоритма SIS от порядка О(N²) до порядка О(N ln N). Поясним этот алгоритм следующим примером.

Предположим, что мы хотим отсортировать последовательность чисел из первой строки на рис. 15. Начнем с предположения, что первый ключ в этой последовательности(38) служит хорошей аппроксимацией ключа, который в конечном счете появится в середине отсортированной последовательности. Используем это значение в качестве ведущего элемента, относительно которого ключи могут меняться местами, и продолжим следующим образом. Устанавливаем два указателя I и J, из которых I начинает отсчет слева (I=1),а J- слева в последовательности (J=N). Сравнивая а_I и а_J. Если а_I≤a_J, устанавливаем J←J−1 и проводим следующее сравнение. Продолжаем уменьшать J до тех пор, пока не достигнем а_I>а_J. Тогда поменяем местами а_I↔a_J (Рис.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).

 

 

Поиск

Теперь обратимся к исследованию некоторых основных проблем, относящихся к поиску информации на стуктурах данных. Как и в предыдущем разделе, посвященному сортировки, будем предполагать, что вся информация хранится в записях, которые можно идентифицировать значениями ключей, т.е. записи R_i соответствует значение ключа,обозначаемое K_i.

Предположим,что в файле расположены случайным образом N записей в виде линейного массива. Очевидным методом поиска заданной записи будет последовательный просмотр ключей. Если найден нужный ключ, поиск оканчивается успешно; в противном случае будут просмотрены все ключи, а поиск окажется безуспешным.Если все возможные порядки расположения ключей равновероятны, то такой алгоритм требует O(N) основных операций как в худшем, так и в среднем случаях. Время поиска можно заметно уменьшить, если предварительно упорядочить файл по ключам. Эта предварительная работа имеет смысл, если файл достаточно велик и к нему обращаются часто.

Далее будем предполагать, что у нас есть N записей, уже упорядоченных по ключам так, что К₁<К₂<…<К_N. Пусть дан ключ К и нужно найти соответствующую запись в файле (безуспешный поиск).

Предположим, что мы обратились к середине файла и обнаружили там ключ K_i. Сравним К и К_i. Если К=К_i, то нужная запись найдена. Если К<К_i,то ключ К должен находиться в части файла, предшествующей К_i (если запись с ключом К вообще существует). Аналогично, если К_i<К, то дальнейший поиск следует вести в части файла, следующей за К_i. Если повторять эту процедуру проверки ключа К_i из середины непросмотренной части файла, тогда каждое безуспешное сравнение К с К_i будет исключать из рассмотрения приблизительно половину непросмотренной части.

Блок-схема этой процедуры, известной под названием двоичный поиск, приведена на рис.16

Algorithm BSEARCH (Binary search- двоичный поиск) поиска записи с ключом К в файле с N≥2 записями, ключи которых упорядочены по возрастанию К₁<К₂…<К_N.

Шаг 0. [Инициализация] Set FIRST←1; LAST← N. (FIRST и LAST- указатели первого и последнего ключей в еще не просмотренной части файла.)

Шаг 1. [Основной цикл ] While LAST≥FIRST do through шаг 4 od.

Шаг 2. [Получение центрального ключа] Set I←|_(FIRST + LAST)/2_|.(К_i- ключ, расположенный в середине или слева от середины еще не просмотренной части файла.)

Шаг 3. [Проверка на успешное завершение ] If К=К_I then PRINT «Успешное окончание, ключ равен К_I»; and STOP fi.

Шаг 4. [ Сравнение] If K < K_I then set LAST←I-1 else set FIRST←I+1 fi.

Шаг 5. [ Безуспешный поиск] PRINT «безуспешно»; and STOP.

Алгоритм BSEARCH используется для отыскания К=42 на рис.17.

Метод двоичного поиска можно также применить для того, чтобы представить упорядоченный файл в виде двоичного дерева. Значение ключа, найденное при первом выполнении шага 2 (К(8)=53), является корнем дерева. Интервалы ключей слева (1,7) и справа (9,16) от этого значения помещаются на стек. Верхний интервал снимается со стека и с помощью шага 2 в нем отыскивается средний элемент (или элемент слева от середины). Этот ключ (К(4)=33) становится следующим после корня элементом влево, если его значение меньше значения корня, и следующим вправо в противном случае. Подынтервалы этого интервала справа и слева от вновь добавленного ключа [(1,3), (5,7)] помещаются теперь на стек.Эта процедура повторяется до тех пор, пока стек не окажется пустым. На рис.18 показано двоичное дерево, которое было бы построено для 16 упорядоченных ключей с рис.17.

Двоичный поиск можно теперь интерпретировать как прохождение этого дерева от корня до искомой записи. Если достигнута конечная вершина, а заданный ключ не найден, искомая запись в данном файле отсутствует. Заметим, что число вершин на единственном пути от корня к заданному ключу К равно числу сравнений, выполняемых алгоритмом BSEARCH при попытке отыскания К.

 

 

 

Да