Алгоритмы сортировки за время O(N)

 

Итак, мы рассмотрели алгоритмы, основанные на операциях сравнения, и для них получили нижнюю оценку времени выполнения. Возникает вопрос, а можно ли на ЭВМ выполнять операцию сортировки быстрее? Здесь следует отметить, что на ЭВМ есть операция, которая принципиально не вписывается в множество рассмотренных операций. Это – операция индексации массива с использованием в качестве индекса функций, вычисляемых от упорядочиваемых элементов. Все алгоритмы, выполняющиеся за время O(N) используют эту операцию.

Сортировка подсчетом

Пусть мы хотим отсортировать N целых чисел A={A1,…, AN}, каждое из которых не превосходит K, при этом K=O(N). Тогда мы можем создать временный массив B размером K, в который можно поместить для каждого i  количество чисел в массиве A, не превосходящих i. Тогда для каждого 1 £ i £ N: в отсортированном массиве в элементе с индексом BA i  лежит элемент, равный Ai .

Итак, приведем реализацию данного алгоритма. Результат будем помещать в третий массив C

CountingSort (A,C, N,K,  B)

 


Для всех i от 1 до K с шагом 1 выполнить: B[i]=0

Для всех i от 1 до N с шагом 1 выполнить: B[A[i]] ++

Для всех i от 1 до N с шагом 1 выполнить: B[A[i]]= B[A[i]]+ B[A[i-1]] 

Для всех i от N до 1 с шагом -1 выполнить: C[B[A[i]]] = A[i]; B[A[i]]- -

 

 


Единственным дополнением к вышеприведенному описанию в этом алгоритме является добавка в его конец `B[A[i]]- -’ . Эта добавка гарантирует, что если в массиве A есть элементы с равными значениями, то они будут положены в различные ячейки массива C. Более того, каждый следующий элемент со значением, равным некоторому x (при обратном проходе!), будет помещаться в ячейку левее предыдущей. Поэтому данная сортировка сохраняет взаимное расположение равных элементов. Этой свойство сортировки называется устойчивостью. Это свойство имеет смысл, когда равенство элементов в смысле сравнения не влечет тождественного равенства элементов. Например, это происходит если сортировка идет по ключу.

Цифровая сортировка

Идея весьма проста. Пусть требуется отсортировать массив целых чисел, записанных в некоторой позиционной системе исчисления. Сначала  мы сортируем массив устойчивым методом по младшей цифре. Потом – по второй, и т.д. Очередная сортировка не меняет порядок уже отсортированных элементов, поэтому в конце мы получим отсортированный массив. Прямой проверкой доказывается следующая

Теорема. Алгоритм цифровой сортировки требует O(nd) операций, где n – максимальное количество операций для одной внутренней сортировки, d – количество цифр.

Этот алгоритм облегчает использование сортировки подсчетом. Действительно, если есть большой массив 32-битных целых чисел без приемлемых ограничений на их величину,  то можно разбить их на 2 либо 4 части и рассмотреть каждую часть как одну цифру в алгоритме цифровой сортировки.

Сортировка вычерпыванием

Пусть требуется отсортировать массив из N вещественных чисел A={A1,…, AN}, равномерно распределенных на интервале [0,1). Идея алгоритма заключается в следующем. Разобьем интервал [0,1) на N равных частей и каждой части сопоставим свой контейнер элементов (например, в самом простом случае, массив вещественных чисел длины N). Каждое число x положим в контейнер с номером [x*N]. После этого отсортируем элементы в каждом контейнере и соберем по порядку элементы из всех контейнеров вместе.

Более конкретно, для реализации контейнеров мы сначала посчитаем, сколько элементов попадет в каждый контейнер, а потом для распределения элементов по контейнерам нам достаточно будет иметь один массив вещественных чисел длины N. Итак, для сортировки массива A, состоящего из N элементов, мы должны завести массивы целых чисел M, I длины N и массив вещественных чисел B длины N.  Пусть функция Sort(B,i0,n) выполняет сортировку пузырьком части массива B , начинающейся с элемента с индексом i0, состоящей из n элементов. Тогда алгоритм имеет следующий вид

SortB (A, N, M, B)

 


Для всех i от 1 до N с шагом 1 выполнить: M[i]=0; I[i]=0; B[i]=0

Для всех i от 1 до N с шагом 1 выполнить: M[A[i]*N+1] ++

Для всех i от 2 до N с шагом 1 выполнить: M[i] = M[i]+ M[i-1]

Для всех i от N до 2 с шагом -1 выполнить: M[i] = M[i-1]

M[0]=0

Для всех i от 1 до N с шагом 1 выполнить: B[M[i]+I[i]+A[i]*N+1]= A[i]; I[i]++

Для всех i от 1 до N с шагом 1 выполнить: Sort(B,M[i],I[i])

Для всех i от 1 до N с шагом 1 выполнить:

    Для всех j от 1 до I[i] с шагом 1 выполнить: A[k]= B[ M[i]+j ]; k++

 

 


Во втором цикле алгоритма мы подсчитываем количество элементов, попавших в i-ый интервал. В третьем и четвертом циклах мы помещаем в M[i] индекс первого элемента части массива B, относящейся к контейнеру с номером i. В пятом цикле мы помещаем элементы в соответствующие контейнеры. В шестом цикле происходит сортировка элементов в контейнерах. Далее мы последовательно выбираем элементы в результирующий массив A.

 

Теорема. Алгоритм SortB работает за время O(N) в среднем, где N – количество сортируемых элементов.

Доказательство. Пусть p=1/N. Вероятность попадания в один контейнер k элементов равна pk=СNk pk (1-p)N-k  (биноминальное распределение).  Время работы алгоритма сортировки в одном контейнере равно S O(k2), где k – количество элементов, попавших в i-ый контейнер.

Согласно свойствам биномиального распределения, среднее (математическое ожидание) количество элементов в контейнере равно M(k)= Sk  pkk=Np=1.  Средне-квадратичное отклонение от среднего значения (дисперсия) количества элементов в контейнере равно D(k)= S k  pk(k- M(k))2=S  k pk(k-1)2=Np(1-p)=1-1/N.

D(k)=M(k2) – (M(k))2  из чего сразу следует M(k2)=D(k) +(M(k))2=2-1/N. Итого, среднее время сортировки одного контейнера равно O(1), а среднее время сортировок N контейнеров равно O(N).

¢