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

2.2  Построение кучи

Для построения кучи из обычного массива достаточно, чтобы для первых floor(n / 2) элементов этого массива выполнилось основное свойство кучи (поскольку остальные элементы не могут содержать потомков, т. е. являются листьями). Для этого мы последовательно, начиная с последних вершин, вызываем функцию heapify() для каждой вершины. Благодаря этому каждый вызов будет работать для вершины, у предков которой основное свойство уже выполнено.

Приведём код на C++.

//Строит в массиве A размера n кучу, возвращая её размер

int buildHeap(int* A, int n)

{

  //Проходим, начиная с последней, все вершины,

  //которые могут иметь потомков

  for (int i = n >> 1; i;)

    heapify(A, n, --i); //восстановим основное свойство

  //Возвращаем размер построенной кучи

  return n;

}

Данный алгоритм, очевидно, работает за время O(nlogn), поскольку n / 2 раз выполняется тело цикла, время работы которого равно O(logn). На самом деле для алгоритма верна более точная оценка O(n). Доказательство этого факта предлагается найти самостоятельно.

2.3  Алгоритм сортировки с помощью кучи

Алгоритм сортировки кучи прост и прозрачен. Сначала необходимо построить кучу в сортируемом массиве. Потом необходимо в цикле менять местами элемент A[1] с последним элементом кучи, уменьшать размер кучи и каждый раз восстанавливать основное свойство кучи для нового элемента A[1]. Таким образом, текущий наибольший элемент кучи каждый раз отправляется в конец кучи, т. е. ставится перед другими бОльшими элементами, а первый элемент снова становится наибольшим среди оставшихся. В итоге массив отсортирован. Всё гениальное просто.

Ниже – код на C++.

//Сортирует массив A размера n

void heapSort(int* A, int n)

{

  //Сначала построим кучу

  buildHeap(A, n);

  //Теперь будем отправлять наибольшие элементы ближе к концу

  //массива и восстанавливать основное свойство оставшейся кучи

  for (int i = n - 1; i; --i) {

    swap(A, A + i); //см. быструю сортировку

    heapify(A, --n, 0);

  }

}

Куча строится за время O(n). Цикл выполняется n – 1 раз, причём трудоёмкость тела цикла равна O(logn). Таким образом, время работы алгоритма сортировки с помощью кучи T(n) = O(nlogn).

3  Сортировки за линейное время

С помощью разрешающих деревьев показано, что без использования внутренней структуры сортируемых данных (при сортировке только с помощью сравнений элементов) сортировка за время, меньшее Ω(nlogn), невозможно. Но добиться линейного времени сортировки (т. е. сортировки за время O(n)) всё-таки можно, используя знания о внутренней структуре сортируемых данных.

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

3.1  Сортировка подсчётом (counting sort)

Данная сортировка оперирует с целыми числами в диапазоне [0..k-1]. Для работы алгоритма за время O(n) должно быть выполнено условие k = O(n).

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

Код на C++ приведён ниже.

//Функция записывает в массив B длиной n отсортированные данные

//из массива A, содержащего целые числа в диапазоне [0..k-1]

void countingSort(const int* A, int* B, int n, int k)

{

  //Выделим массив для хранения кол-ва предшествующих чисел

  int *C = (int*)std::calloc(k, sizeof(int));

  //Сначала сохраним для каждого числа кол-во его вхождений в массив

  for (int i = 0; i < n; ++i)

    ++C[A[i]];

  //Потом преобразуем массив C так, что для каждого числа будет