8. можно ли элементы сравнивать параллельно.
Очевидно, что с отсортированными данными работать легче, чем с произвольно расположенными. Когда элементы отсортированы, их проще найти (как в телефонном справочнике), обновить, исключить, включить и слить воедино. На отсортированных данных легче определить, имеются ли пропущенные элементы (как в колоде игральных карт), и удостовериться, что все элементы были проверены. Легче также найти общие элементы двух множеств, если они оба отсортированы. Сортировка применяется при трансляции программ, когда составляются таблицы символов; она также является важным средством для ускорения работы практически любого алгоритма, в котором часто нужно обращаться к определенным элементам.
Обычно сортируемые элементы представляют собой записи данных определенного вида. Каждая запись имеет поле ключа и поле информации. Поле ключа содержит положительное число, обычно целое, и записи упорядочиваются по значению ключа.
В этом разделе мы рассматриваем два из наиболее эффективных алгоритмов сортировки, быстрой сортировки и сортировки пирамидой (QUICKSORT и HEAPSORT), и устанавливаем теоретически не улучшаемые границы для всех алгоритмов сортировки с помощью сравнений. В других разделах обсуждаются еще два алгоритма сортировки: сортировка простыми включениями (SIS) и параллельная сортировка (PARSORT).
Сортировка методом прямого включения
Сортировка методом прямого включения работает со списком неупорядоченных положительных целых чисел (обычно называемых ключами), сортируя их в порядке возрастания. Это делается примерно так же, как большинство игроков упорядочивают сданные им карты, поднимая каждый раз по одной карте. Покажем работу общей процедуры на примере следующего неотсортированного списка из восьми целых чисел:
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
В следующем алгоритме заводится только один список, и переорганизация чисел производится в старом списке.
AlgorithmSIS( Сортировка Прямым включением). Отсортировать на старом месте последовательность целых чисел I(1), I(2), . . . ,I (N) в порядке возрастания (рис. 11).
Шаг 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. [ Включение ] SetI(L+1)←K.
QUICKSORT: Алгоритм сортировки со средним временем работы О(NlnN)
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.