Алгоритмы сортировки. Быстрая сортировка (quicksort). Сортировка с помощью кучи (heapsort). Сортировки за линейное время, страница 4

  //храниться информация о количестве предшествующих ему чисел

  for (int j = 1; j < k; ++j)

    C[j] += C[j - 1];

  //В конце выведем в массив B числа точно на нужные позиции

  while (n--)

    B[--C[A[n]]] = A[n];

  //В C++ за вами мусор никто не соберёт...

  std::free((void *)C);

}

Первый и третий циклы в приведённом выше коде выполняются за время Θ(n), а второй цикл и операция выделения памяти – за время Θ(k) (операцию выделения памяти можно убрать, если массив расположить в статической памяти и обнулять перед каждым использованием за время Θ(k)). Если k = O(n), время выполнения алгоритма T(n) = Θ(n). По сравнению с сортировкой вставками этот результат кажется сверхбыстрым. Хотя для такой быстроты необходимо, чтобы и данные соответствовали требованиям к структуре данных (в данном случае – были бы целыми числами в определённом диапазоне размера O(n)).

Кроме всего вышесказанного, алгоритм сортировки подсчётом обладает свойством, называемым устойчивостью (is stable). Это означает, что порядок следования равных элементов остаётся неизменным, что особенно полезно при сортировке записей по одному из полей (сохраняется сортировка по другому полю).

3.2  Цифровая сортировка (radix sort)

Сортировка  подсчётом очень хорошо подходит для сортировки целых чисел из диапазона малого размера, поскольку ей требуется Θ(k) дополнительной памяти. Но вот если вы, скажем, захотите с её помощью отсортировать массив 32-битных целых, вам потребуется выделять 4 гигабайта дополнительной памяти. Цифра эта не очень-то радует. Но не надо выбрасывать алгоритм, который не всегда работает хорошо. Надо просто попробовать использовать его в составе алгоритма, который работает хорошо. Таким алгоритмом и является алгоритм цифровой сортировки.

При цифровой сортировке вы сортируете числа по разрядам. Сначала сортируете все числа в сортируемом массиве A по младшему разряду, затем по следующему по старшинству разряду и так далее, пока не пройдёте все разряды.

Ниже приведён пример такой сортировки. В примере первый столбец не отсортирован, второй отсортирован по первому разряду, третий – по второму, а четвёртый – по первому.

708          340          708          208

576          291          208          209

340          982          209          291

208          444          340          340

899          576          444          377

444          377          576          444

291          708          377          576

377          208          982          708

209          899          291          899

982          209          899          982

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

В таком случае, если количество разрядов d постоянно, а размер системы счисления k = O(n), то алгоритм работает за время T(n) = O(d (n + k)) = O(dn) = O(n).

В цифровой сортировке очень важно выбрать размер системы счисления k таким образом, чтобы соотношение d и количества используемой памяти было оптимальным.

4  Домашнее задание

1.  Докажите, что если массив состоит из одинаковых элементов, время выполнения функции quickSort() равно Θ(nlogn), а если массив отсортирован в убывающем порядке – Θ(n²).

2.  Измените функцию heapify(), заменив рекурсию циклом.

3.  Докажите, что алгоритм сортировки подсчётом является устойчивым.

4.  Реализуйте цифровую сортировку на C++ для типа long (или int, если на вашей машине он 32-разрядный). Ваша реализация должна сортировать и отрицательные целые.

5  Список литературы

Т. Кормен, Ч. Лейзерсон, Р. Ривест [2001], Алгоритмы. Построение и анализ, МЦНМО, М., 135–179

Дональд Э. Кнут [2000], Искусство программирования, третье издание. Том 3: Сортировка и поиск, Вильямс, 92-424