7.2. Рекурсивные алгоритмы сортировки

Рекурсия естественным образом «всплывает» в сортировках, основанных на перераспределении элементов исходной последовательности: их разделении на части и обратном слиянии. В процессе разделения к полученным частям применяется тот же самый алгоритм до тех пор, пока не получатся части единичной (или нулевой) размерности, «сборка» (слияние) частей осуществляется в обратном порядке – после возвращения из рекурсивного вызова.

(рисунок).

Аналогично тому, как сортировки выбором и вставкой основаны на одной идее (перенос на каждом шаге по одному элементу из неупорядоченной последовательности в упорядоченную), но противоположны по способу его реализации, сортировки рекурсивным разделением и рекурсивным слиянием противоположны по тому, на какой стадии реализуется идея упорядоченности и происходит перестановка элементов. В рекурсивном разделении частичная упорядоченность устанавливается в процессе разделения путем разбиения исходной последовательности (массива, списка) на две части по принципу «меньше-больше» некоторого срединного значения, называемого медианой. Способ получения такого значения и соразмерность полученных частей не имеют принципиального значения (среднее арифметическое, просто значение любого из элементов последовательности). Обратное объединение разделенных частей уже не связано с перестановкой элементов и происходит по принципу «левая-медиана-правая».

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

Наиболее очевидный способ разделения состоит в просмотре разделяемого интервала с двух концов таким образом, чтобы в процессе движения слева и справа от текущих индексов оставались разделенные части. Для этого оба индекса должны продвигаться к центру, если под ними находятся элементы, соответственно, меньшие и большие медианы. Это продолжается, пока они оба не остановятся. В этом случае нужно поменять местами оба «неправильно» расположенных элемента и продолжить разделение. В приведенном примере в качестве медианы используется значение среднего арифметического на разделяемом интервале (a,b), причем значения, равные среднему, попадают в правую часть. Рекурсия завершается, когда размерность интервала будет равна 1 или 0, а также, если все значения на интервале равны.

//------------------------------------------------------72-01.cpp
//------- Сортировка массива рекурсивным разделением
// В качестве медианы - среднее арифметическое
void sort(int in[], int a, int b) {
  int i,j,mode;
  double sr=0;
  if (a>=b) return;  // Размер части =0
  for (i=a; i<=b; i++) sr+=in[i];
  sr=sr/(b-a+1);
  for (i=a, j=b; i <= j;) {
    if (in[i]< sr) { i++; continue; }   // Слева - меньше, пропустить
    if (in[j]>=sr) { j--; continue; }   // Справа - больше, пропустить
    int c = in[i]; in[i] = in[j]; in[j]=c;
    i++,j--;  // Поменять местами и пропустить
  }
  if (i==a) return;  // все равны и в правой части
  sort(in,a,j); sort(in,i,b);  // рекурсивный вызов для двух частей
}

«Быстрая» сортировка использует в качестве медианы первый элемент на разделяемом интервале (in[a]). Сравнение медианы производится с элементом в противоположном конце массива (i=a, j=b).Если они больше медианы, то они пропускаются (j--), иначе производится обмен медианы с «неправильно» размещенным элементом, и аналогичное «действо» производится с другого конца. Элегантность алгоритма проявляется в том, что в обоих случаях расположения медианы работает одно и то же тело цикла, в котором текущее местоположение медианы (справа или слева) и направление сокращения интервала обозначается признаком mode. В результате разделения медиана занимает в массиву позицию in[i].

//------------------------------------------------------72-02.cpp
//-------"Быстрая" сортировка
void sort(int in [], int a, int b) {
  int i, j, mode;

  if (a >= b) return; // Размер части =0

  for (i = a, j = b, mode = 1; i < j; mode > 0 ? j-- : i++) // Сокращение слева или справа

    if ( in [i] > in [j]) { // Очередной не на своем месте
      int c = in [i]; in [i] = in [j]; in [j] = c; // Перестановка медианы с концевым

      mode = -mode; // элементом со сменой сокращаемого конца

    }

  sort( in , a, i - 1);
  sort( in , i + 1, b); // рекурсия для частей БЕЗ медианы
} 

Очевидно, что медиана делит массив на две неравные части. Алгоритм разделения можно выполнить итерационно, применяя его к той части массива, которая содержит его середину (по аналогии с двоичным поиском). Тогда в каждом шаге итерации медиана будет сдвигаться к середине массива.

Рекурсивное разделение односвязного списка. Рекурсивное разделение элегантно выглядит в односвязном списке, поскольку изменение логического порядка следования элементов в нем можно достигнуть переустановкой указателей. Тем более, что в процессе разделения порядок помещения элементов в разделяемые части не является важным, то есть очередной элемент разделяемого списка можно поместить в начало одного из двух выходных с использованием всего двух операций присваивания указателей. В качестве медианы берется значение первого элемента разделяемого списка.

//---------------------------------------------------------72-03.cpp
//  сортировка односвязного списка рекурсивным разделением
list* sort(list * p) {
  list * m, * p1, * p2, * q;

  if (p == NULL || p -> next == NULL)
    return p; // не более одного - конец разделения

  m = p;
  p = p -> next; // m-медиана - первый элемент
  p1 = p2 = NULL; // p1,p2 - разделенные списки

  while (p != NULL) {
    q = p;
    p = p -> next; // извлечь очередной из входного

    if (q -> val < m -> val) // q – очередной, p – остаток списка
      q -> next = p1, p1 = q; // меньше медианы - в начало первого
    else
      q -> next = p2, p2 = q; // иначе - в начало второго
  }

  p1 = sort(p1); // рекурсивная сортировка частей
  p2 = sort(p2);
  m -> next = p2; // "склеить" медиану и второй список

  if (p1 == NULL) return m; // первый - пустой

  for (q = p1; q -> next != NULL; q = q -> next);

  q -> next = m; // иначе, дойти до конца первого,
  return p1; // присоединить к нему медиану
} // со вторым списком и вернуть

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

Сортировка рекурсивным слиянием. Если перенести «центр тяжести» на процесс слияния, то разделение последовательности станет простой формальностью: она просто «режется» на две части строго посередине. Это будет происходить до тех пор, пока не получатся части единичной или нулевой размерности. Содержательная сторона алгоритма будет заключаться в слиянии, которое будет выполняться в обратном порядке в процессе возвратов из рекурсивных функций (Если в тексте функции рекурсивного разделения вызов функции находится в конце текста, то в рекурсивном слиянии – в начале). Сама процедура слияния описана в 4.6: для получения одной упорядоченной последовательности из двух достаточно одного цикла, на каждом шаге которого выбирается (сливается) один элемент из пары «верхних».

Рекурсивное слияние массива.

//---------------------------------------------------------72-04.cpp
// Сортировка массива рекурсивным слиянием
void sort(int A[], int a, int b) {
  if (a >= b) return; // Разделение закончилось

  int m = (a + b + 1) / 2, i, j, k; // Нет - взять середину интервала

  sort(A, a, m - 1); // Рекурсивный вызов для частей
  sort(A, m, b);

  int * tmp = new int[b - a + 1]; // Слияние частей во временный массив

  for (i = a, j = m, k = 0; k <= b - a; k++)
    if (i == m || j != b + 1 && A[j] < A[i])
      tmp[k] = A[j++]; // слить из второй части, если
    else // первая кончилась или во второй меньше
      tmp[k] = A[i++]; // слить из первой части

  for (i = a, j = 0; i <= b; i++, j++)
    A[i] = tmp[j]; // вернуть слитые части обратно в A

  delete tmp;
} // удалить временный массив

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

//---------------------------------------------------------82-05.cpp
//  сортировка односвязного списка рекурсивным слиянием
list * sort(list * p) {
  list * out, * p1, * p2, * q;

  if (p == NULL || p -> next == NULL) // не более одного - конец разделения
    return p; // найти середину, p2 движется в 2 раза

  p1 = p2 = p; // "быстрее" p1 

  while (p2 -> next != NULL && p2 -> next -> next != NULL) {
    p1 = p1 -> next; // 1-2-3-4-5-6-7 ==> 1-2-3-4 || 5-6-7
    p2 = p2 -> next;
    p2 = p2 -> next;
  }

  q = p1 -> next; // разделение списка на две части

  p1 -> next = NULL;

  p = sort(p); // рекурсивная сортировка частей
  q = sort(q);

  list OUT; // для выходного списка - фиктивный

  p1 = & OUT; // "последний" элемент

  while (p != NULL || q != NULL) // пока оба списка не пусты
  { // второй пуст или в первом меньше, чем во втором

    if (q == NULL || p != NULL && p -> val < q -> val)
      p1 -> next = p, // перенести из первый из первого списка
      p1 = p1 -> next, // в конец выходного
      p = p -> next;
    else
      p1 -> next = q, // перенести из первый из второго списка
      p1 = p1 -> next, // в конец выходного
      q = q -> next;
  }

  return OUT.next;
}

Трудоемкость рекурсивных сортировок. При сортировке рекурсивным разделением в идеальном случае, когда каждое разделение будет производиться строго на две равные части, мы получим две задачи половинной размерности (N/2), причем количество операций будет пропорционально N: N-1 сравнений или максимум N/2 обменов (в среднем N/4). Тогда для T_N=2T_{N/2} + N получим T=N log_2 N (см.8.1). В наихудшем случае, когда все элементы будут попадать в один интервал, а другой будет оставаться пустым, размерность будет уменьшаться всего на 1, тогда для T_N=T+{N-1} + N получим T=N^2/2. Самое парадоксальное, что такое разделение будет происходить на уже упорядоченном массиве (плюс на плюс дает минус ☺). Сортировка рекурсивным слиянием ввиду равномерности разделяемых частей близка к идеалу T=N log_2 N, однако требует дополнительной памяти для сливаемых частей.