Главная » Java, Структуры данных и алгоритмы » Сортировка, множества и выборка

0

Второй закон термодинамики предполагает, что природа тяготеет к беспорядку, люди же предпочитают упорядоченность. И в самом деле, хранение данных в определенном порядке имеет ряд преимуществ. Например, бинарный поисковый алгоритм, приведенный в разделе 8.2, корректно работает только для упорядоченных векторов. Поскольку компьютеры предназначены для обеспечения деятельности человека, эта глава посвящена изучению сортирующих алгоритмов и их применению. Напомним, что проблема сортировки выглядит следующим образом. Допустим, S — последовательность из п элементов, которые можно сравнивать друг с другом в соответствии с их отношениями упорядоченности, то есть всегда возможно сравнить два элемента, чтобы определить, какой из них больше или меньше, или они равны. Задача состоит в реорганизации последовательности таким образом, чтобы элементы располагались в возрастающем (или в неубывающем, если они равны) порядке.

Читатель уже знаком с несколькими алгоритмами сортировки. В частности, в п. 7.1.2 приведена простая схема сортировки под названием PriorityQueueSort, состоящая из ввода элементов в приоритетную очередь и последующей выборки их в неубывающем порядке серией операций removeMin. Если приоритетная очередь реализована последовательностью, то PriorityQueueSort выполняется за 0(п2) времени и соответствует методу сортировки ввода либо сортировки выбора, в зависимости от вида последовательности, и виду приоритетной очереди — сортированная или несортированная (п. 7.2.3). Если же приоритетная очередь реализована пирамидой (раздел 7.3), то PriorityQueueSort выполняется за 0(п log п) времени и соответствует методу пирамидальной сортировки (п. 7.3.4).

В этой главе описаны еще четыре алгоритма сортировки: сортировка методом слияния (merge-sort), быстрая сортировка (quicksort), сегментная сортировка (bucket-sort) и поразрядная сортировка (radix-sort). Кроме того, здесь представлен новый абстрактный тип данных «множество» (set) и показано, как используемая в алгоритме техника сортировки методом слияния может применяться при реализации методов этого АТД. На протяжении всей главы полагаем, что элементы находятся в упорядоченных сортированных отношениях. Кроме того, считаем, что для сравнения используется компаратор (п. 7.1.4), и в этом случае процедура сравнения занимает 0(1) времени.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии