Алгоритм быстрой сортировки чисел

Какой алгоритм сортировки является самым быстрым? Задайте этот вопрос любой группе программистов, и вы получите оживленную дискуссию. Конечно, единого ответа не существует. Это зависит не только от алгоритма, но и от компьютера, данных и реализации. Однако если подсчитать количество операций, необходимых для сортировки целых чисел на стандартном компьютере фон Неймана, то явный победитель — алгоритм, представленный в статье «Сортировка в линейное время?» А. Андерссона, Т. Хагерупа, С. Нильссона и Р. Рамана (Proceedings of the 27th Annual ACM Symposium on the Theory of Computing, 1995). Он сортирует n целых чисел за время, пропорциональное n log log n. В этой статье я дам вам полное описание этого алгоритма.

Можно ли сделать это еще быстрее? Никто не знает. Мы знаем только, что это невозможно сделать, используя менее n операций: Алгоритм, использующий меньшее число операций, не может просмотреть каждое из n чисел и, следовательно, может оставить некоторые из них не по порядку.

Несмотря на то, что алгоритм сортировки по времени n log log n возник как теоретическая игра, в реальной жизни он работает хорошо. Реализация на языке Си, например, nloglogn.c без особых оптимизаций работает на типичной 32-битной машине быстрее, чем многие стандартные алгоритмы сортировки из учебников.

Проблема

Чтобы достичь согласия при обсуждении скорости алгоритма сортировки, необходимо установить некоторые точки соприкосновения. Как мы измеряем скорость? Существует устоявшаяся модель — компьютер фон Неймана, или модель оперативной памяти с единичной стоимостью — широко используемая компьютерными учеными для оценки алгоритмов без введения всех сложностей реальных компьютеров. Эта модель не учитывает некоторые важные вещи, такие как разрыв в производительности между оперативной памятью и центральным процессором, но обычно дает хорошее приближение к реальной производительности.

В модели стоимости единицы оперативной памяти нет ничего странного. Вероятно, она похожа на ваш мысленный образ компьютера. В компьютере есть оперативная память, разделенная на слова по w бит — «длина слова» машины. Каждое слово имеет адрес, и доступ к слову можно получить за постоянное время, учитывая его адрес. Компьютер имеет центральный процессор, способный выполнять небольшое количество инструкций, таких как чтение и запись слов в оперативной памяти, а также выполнение основных арифметических и логических операций. Каждая из этих операций может быть выполнена за постоянное число машинных циклов.

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

Другие методы сортировки могут быть быстрее. Например, используя радиксную сортировку, можно отсортировать целые числа размером в n слов, сканируя данные по несколько бит за раз. Каждое сканирование может быть выполнено за линейное время, а количество сканирований зависит от длины слова w. Следовательно, время радиксной сортировки пропорционально nw. Здесь легко допустить ошибку. На большинстве компьютеров w — небольшое число (обычно 32 или 64), и у вас может возникнуть соблазн заявить, что радиксная сортировка — это алгоритм сортировки с линейным временем. Это не так. Алгоритм будет работать, только если w ≥ log n. В противном случае вы даже не сможете хранить числа. Поскольку каждый адрес памяти представляет собой слово, состоящее из w бит, адресное пространство не сможет вместить n чисел, если w < log n. Следовательно, в модели с единичной стоимостью оперативной памяти радиксная сортировка также выполняется за время, пропорциональное n log n.

Теперь я опишу алгоритм, который не зависит от длины слова. Для любой длины слова w, w ≥ log n, он сортирует целые числа размером в n слов за время, пропорциональное n log log n.
Алгоритм

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

На втором этапе вы выполняете сортировку слиянием сокращенных чисел. Поскольку числа стали намного короче, несколько чисел помещаются в одно машинное слово. При наличии нескольких чисел в одном слове можно параллельно выполнять несколько операций над этими числами, используя сдвиг и побитовые операции AND/OR/XOR, которые есть в большинстве компьютеров. Фактически, используя схему, известную как «упакованное слияние», можно объединить две отсортированные последовательности из k чисел, каждое из которых помещается в одно слово, за время, пропорциональное log k. Это улучшение по сравнению со стандартным алгоритмом слияния, который требует времени, пропорционального k.

Учитывая эти строительные блоки, мы почти закончили. На первом этапе вы выполняете log log n сокращений. Это делается за время n log log n, поскольку каждое сокращение занимает линейное время. После уменьшения количества битов вдвое log log n раз, числа будут настолько малы, что в одном слове можно уместить k = log n чисел.

На втором этапе вы используете упакованное объединение как подпрограмму в стандартном mergesort. Слияние выполняется снизу вверх. Начните с сортировки подпоследовательностей длины k. Каждая из n/k подпоследовательностей сортируется за k log k времени с помощью стандартного алгоритма, основанного на сравнении, например mergesort. Подставляя k = log n, вы видите, что это составляет n log log n.

Теперь вы объединяете эти отсортированные последовательности попарно, используя упакованное объединение, и таким образом создаете более длинные отсортированные последовательности. Каждая последовательность упаковывается в одно машинное слово. В этом первом раунде необходимо объединить n/2k пар, каждое объединение выполняется за log k времени с использованием упакованного объединения. В сумме получается n/2k × log k.

В следующем раунде необходимо объединить n/4k пар, каждая из которых состоит из двух слов. Это делается за n/4k × 2 log k = n/2k × log k времени, то есть за то же время, что и раньше. Фактически, вы получите один и тот же результат для каждого раунда.

Поскольку длина последовательностей удваивается в каждом раунде, количество раундов равно log n/k. Следовательно, общее время для этой версии mergesort равно log n/k × n/2k × log k. Подставляя k = log n, вы видите, что это выражение также не превышает n log log n.

На этом этапе данные отсортированы, и прошло не более n log log n времени, поскольку и фаза уменьшения, и фаза слияния-сортировки выполняются за время, пропорциональное n log log n.
Уменьшение размера числа

Существует несколько альтернативных алгоритмов, которые могут быть использованы для сокращения задачи сортировки до задачи с более короткими числами. Выбор зависит от того, хотите ли вы оптимизировать скорость сокращения, скорость работы алгоритма или объем требуемой памяти. Здесь я покажу вам простой алгоритм, который уменьшает количество битов в 2 раза. Он выполняется за линейное время, но использует много памяти.

Предположим, что вам нужно отсортировать n b-битных чисел. Я буду использовать схему сортировки с двумя таблицами ведер: High и Low. Каждая запись таблицы может содержать связанный список чисел. Я объясню алгоритм на небольшом примере. На этом рисунке показаны семь 6-битных чисел, которые нужно отсортировать.

Данные: 100101, 011001, 100111, 001100, 011111, 110111, 001000

Высокий Низкий


000: 000:
001: 001100, 001000 001:
010: 010:
011: 011001, 011111 011:
100: 100101, 100111 100:
101: 101:
110: 110111 110:
111: 111:

Пакет: 100, 011, 001, 110

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

Первым шагом является выполнение сортировки по старшим битам; в нашем примере — по первым 3 битам каждого числа. Каждый раз, когда ведро используется в первый раз, номер этого ведра записывается в пакетный список.

На следующем рисунке показан второй шаг алгоритма, на котором вы обходите каждое непустое ведро в таблице High bucket, перемещая элементы в таблицу Low bucket. Следует отметить несколько важных моментов.

Высокий Низкий.


000: 000:
001: 001000 001:
010: 010:
011: 011001 011:
100: 100101 100: 001100
101: 101:
110: 110111 110:
111: 111: 100111, 011111

Партия: 100, 011, 001, 110, 111, 100

Вы используете партию для поиска непустых ведер. Таким образом, вся операция может быть выполнена за линейное время.
Когда ведро Low используется в первый раз, оно записывается в пакет.
Все элементы не перемещаются. Минимальный элемент в каждом High bucket оставляется. Это очень важно. Пакет будет нашей сокращенной задачей сортировки, и он не должен содержать более n элементов. Оставляя один элемент в каждом непустом ведре High, вы гарантируете, что общее количество непустых ведер, а значит, и количество записей в партии, не превышает n.

Следующим шагом будет сортировка партии. Это сокращенная задача сортировки — партия содержит не более n чисел, и каждое число имеет b/2 бит.

Используя отсортированную партию, легко собрать числа в порядке возрастания. Вы начинаете с перемещения чисел из списка Low bucket list в список High bucket list. В результате получается вот такой рисунок.

Высокий Низкий


000: 000:
001: 001000, 001100 001:
010: 010:
011: 011001, 011111 011:
100: 100101, 100111 100:
101: 101:
110: 110111 110:
111: 111:

Пакет: 001, 011, 100, 100, 110, 111


И снова вы используете пакет для поиска непустых ведер. Но поскольку пакет теперь отсортирован, Низкие ведра будут посещаться по порядку. Следовательно, каждое ведро High в итоге будет содержать отсортированный список.

Наконец, вы обходите непустые ведра High, снова используя отсортированную партию, чтобы получить окончательный отсортированный список.

Возможно, вы заметили проблему в этом алгоритме. Как узнать, что ведро пусто? Очевидное решение — инициализировать каждое ведро нулевым указателем. Но вы не можете себе этого позволить: Количество ведер может быть больше n, а алгоритм должен выполняться за линейное время. Решение немного сложное; см. раздел «Как избежать инициализации памяти».
Быстрое объединение коротких чисел

Осталось только быстро объединить короткие последовательности коротких чисел. Идея состоит в том, чтобы использовать параллельный алгоритм, требующий только очень простых операций. Если алгоритм достаточно прост, можно смоделировать параллелизм, используя параллельность, присущую побитовым логическим операциям. Например, операция побитового ИЛИ выполняет параллельно w операций ИЛИ всего за один машинный цикл.

Битоническое объединение Батчера удовлетворяет этим требованиям. Алгоритм основан на свойстве так называемых «битоновых последовательностей». Битоническая последовательность почти отсортирована: Она является конкатенацией восходящей и нисходящей последовательности или может быть получена путем вращения (циклического сдвига) такой последовательности. Например, последовательность 2, 3, 4, 3, 2, 1 является битонической, поскольку она представляет собой соединение восходящей последовательности 2, 3, 4 и нисходящей последовательности 3, 2, 1. Последовательность 3, 4, 3, 2, 1, 2 также является битонической, поскольку она может быть получена путем вращения предыдущей битонической последовательности. Битонические последовательности обладают особым свойством, описанным в этой лемме:

Лемма: Если последовательность x1, x2, ..., x2k является битонической, то две последовательности L = min(x1, xk+1), min(x2, xk+2), ..., min(xk, x2k) и R = max(x1, xk+1), max(x2, xk+2), ..., max(xk, x2k) также являются битоническими. Более того, каждый элемент L меньше или равен каждому элементу R. 

Другими словами:

Начните с любой битонической последовательности с четным числом элементов, разрежьте ее пополам и сформируйте две новые последовательности, сравнивая обе половины элемент за элементом.
Сформируйте одну последовательность, L, содержащую минимальные элементы из каждой пары, и другую, R, содержащую максимальные элементы.
Тогда последовательности L и R будут битоническими и каждый элемент L будет меньше или равен каждому элементу R.

Используя эту лемму, можно эффективно объединять отсортированные последовательности. Например, поменяв местами одну последовательность на этом рисунке

X = 0, 2, 3, 5
Y = 2, 3, 6, 7

// Сформируем битоновую последовательность S, перевернув X и добавив Y:
S = 5, 3, 2, 0, 2, 3, 6, 7

// Вычислите минимальную и максимальную последовательности L и R:
L = min(5, 2), min(3, 3), min(2, 6), min(0, 7) = 2, 3, 2, 0
R = max(5, 2), max(3, 3), max(2, 6), max(0, 7) = 5, 3, 6, 7

и, добавляя одно к другому, получаем битоновую последовательность. На первом этапе объединения вы используете лемму для получения двух подпоследовательностей L и R, где каждый элемент L не больше каждого элемента R. Чтобы завершить объединение, вам нужно только отсортировать L и R и объединить эти две последовательности. Это можно сделать, снова используя лемму. Помните, что и L, и R являются битоническими, поэтому на втором этапе можно применить битоническую лемму к каждой из них. Процесс повторяется рекурсивно до тех пор, пока подпоследовательности не будут состоять только из одного элемента.

Упаковав все числа в одно машинное слово, можно выполнить каждую фазу этого алгоритма объединения за постоянное время.

A = 0101 0011 0010 0000 0000 0000 0000 0000 // 5 3 2 0 0 0 0 0
B = 0010 0011 0110 0111 0000 0000 0000 0000 // 2 3 6 7 0 0 0 0

// Вычислите битовую маску N, показывающую, какие элементы A.
// меньше или равны соответствующим элементам B.
// M — предварительно вычисленная константа.

M = 1000 1000 1000 1000 1000 1000 1000 1000 // 8 8 8 8 8 8 8 8
N = ((B ИЛИ M) — A) И M // 0 8 8 8 8 8 8 8 8 8 8 8
N = N — (N>>3) // 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7.

// Вычислите последовательность max и min и конкатенируйте их.

Z = (B И N) // 0 3 6 7 0 0 0 0
ИЛИ (A — (A И N)) // 5 0 0 0 0 0 0 0
ИЛИ ((A И N)>>16) // 0 0 0 0 0 3 2 0
ИЛИ ((B — (B И N))>>16) // 0 0 0 0 2 0 0 0

В этом примере числа состоят из 3 битов. Вам также понадобится специальный тестовый бит для каждого числа, поэтому в одно 32-битное слово можно уместить восемь чисел. Специальная битовая маска N, указывающая, какие элементы меньше, вычисляется с помощью вычитания и основных побитовых операций AND/OR. Вторая фаза объединения может быть выполнена аналогичным образом. Фактически, обе подпроблемы могут быть решены параллельно с использованием той же техники. (Все подробности можно найти в nloglogn.c.).

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


Спасибо что пользуетесь сайтом best-exam. Поделитесь сайтом с друзьями!
Подписаться
Уведомить о
0 комментариев
Межтекстовые Отзывы
Посмотреть все комментарии