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

0

В предыдущем разделе показано, что для выполнения алгоритма сравнительной сортировки последовательности из п элементов максимально требуется Q(n log п) времени. Вполне закономерен вопрос о наличии других алгоритмов, позволяющих работать быстрее, чем за 0(п log п). Известно, что такие алгоритмы существуют, но для них требуются определенные предварительные условия. И даже с учетом этого такие алгоритмы часто используются в практике, и с ними следует ознакомиться. В этом разделе рассматривается проблема сортировки последовательности объектов, каждый из которых является парой «ключ-элемент».

Рассмотрим последовательность S из п элементов, ключами которых являются целые числа в пределах [О, N— 1] при N> 2, и предположим, что S должна быть отсортирована согласно ключам объектов. В таком случае последовательность S может быть упорядочена за 0(п + N) времени. Это может показаться неожиданным, но, например, если N равно 0(п), то сортировка Sзаймет О(п) времени. Естественно (и важно), это зависит от формата элементов, ri можно отказаться от сравнений.

Речь пойдет об алгоритме под названием сегментная сортировка (bucket-sort), в основу которого положено не сравнение, а применение ключей в качестве индексов в массиве сегментов В, содержащем объекты от 0 до N – 1. Объект с ключом к помещается в сегмент В[к], который также является последовательностью (объектов с ключом к). После передачи каждого объекта исходной последовательности S в каждый сегмент можно отправить объекты обратно в S в сортированном порядке путем нумерации содержимого сегментов по порядку: 5[0], В[ 1], …, B[N- 1]. Алгоритм сегментной сортировки приводится во фрагменте кода 10.8.

Алгоритм bucketSort(5):

Input: последовательность S объектов с целочисленными ключами в пределах [0, N-1].

Output: последовательность отсортированная в возрастающем порядке.

// Пусть В есть массив из N последовательностей с целочисленными // ключами, каждая из которых изначально пуста, for каждого объекта х в S do // допустим, к — ключ для х

II удалить х из S и вставить его в хвост сегмента (последовательности) В[/с] for / <— 0 to Л/ – 1 do

for каждого объекта х в последовательности В[/] do // удалить х из В[/] и вставить его в хвост S

Фрагмент кода 10.8.

Легко заметить, что сегментная сортировка выполняется за 0(п + N) времени и занимает 0(п + N) места. Следовательно, такая сортировка вполне применима в случаях, когда Допредельное значение ключей) невелико по сравнению с размером последовательности п, скажем, N= О(п)

17 Зак. 2456

или N = 0(п log п). Однако по мере увеличения N производительность ухудшается.

Важным свойством алгоритма сегментной сортировки является его корректная работа даже при наличии большого количества различных элементов с одинаковыми ключами.

Стабильная сортировка

При сортировке пар «ключ-элемент» возникает серьезная проблема обработки одинаковых ключей. Допустим, S= ((ко, ео), …, (кп_ еп_ i)) — последовательность объектов. Будем считать, что алгоритм работает стабильно, если для любых двух объектов (kj, eft и (kj, ej) последовательности S ключи kj = kj, a (kj, ej) предшествует (kj, ej) до сортировки (то есть / < j) и после сортировки. Стабильность важна для алгоритма сортировки, потому что приложениям может понадобиться первоначальный порядок элементов с одинаковыми ключами.

Приведенная вб фрагменте кода 10.8 сегментная сортировка не гарантирует стабильности. Хотя это не является наследуемым свойством самого метода сегментной сортировки, можно модифицировать приведенное описание для придания методу стабильности, сохранив при этом время выполнения 0(п + N). Добиться стабильности сегментной сортировки можно, если всегда удалять первый элемент из последовательности S и из последовательности B[i] во время выполнения алгоритма.

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

По теме:

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