Веселые перестановки. Решение (сортировка перестановками соседних элементов)

Итак, мое решение вопроса о приведении одной последовательности к другой, когда можно только переставлять два элемента.

Нас просят привести одну последовательность (исходную) к другой (целевой). То есть логично предположить, что одна последовательность в нужном порядке (целевая), а вторая (исходная) - нет. Так надо просто отсортировать исходную последовательность "в целевую".

Так как целевая последовательность по условию не обязательно отсортированная, то при сортировке "к ней" нельзя просто сравнивать элементы исходной последовательности на больше/меньше, так как в этом случае мы получим на выходе сортировку по правилам системы исчисления. В нашем случае надо принять, что целевая последовательность и есть эталонный отсортированный алфавит, и он задает правила сортировки. При сравнении значений из этого алфавита надо понять, в какой позиции алфавита находится значение и использовать его индекс как ключ сортировки (функция less()).

Теперь, а какой алгоритм сортировки использовать, чтобы для перемещения элементов использовать только обмен соседних элементов (функция swap())? Подходит сортировка вставками, когда на каждом шаге неотсортированный элемент последовательно "пропихивается" вниз к отсортированным. Тут как раз можно обойтись только обменом соседних элементов. Сама функция insertion_sort() является универальной и не зависит от компаратора is_less().

#include <stdlib.h>
#include <stdio.h>

void swap(int* a, int i) {
  int t = a[i];
  a[i] = a[i + 1];
  a[i + 1] = t;
}

#define N 8

const int etalon[] = { 1, 5, 7, 4, 2, 9, 8, 6 };
int from[N] = { 8, 1, 4, 2, 5, 6, 9, 7 };

void insertion_sort(int* a, int n, int (*is_less)(int, int)) {
  int i, j;
  for (i = 1; i < n; ++i) 
    for (j = i - 1; j >= 0 && is_less(a[j + 1], a[j]); j--)
      swap(a, j);
}

void print_array(const char* title, const int* a, int n) {
  int i;
  printf("%9s: ", title);
  for (i = 0; i < n; ++i)
    printf("%d ", a[i]);
  printf("\n");
}

int less(int a, int b) {
  int ia = -1, ib = -1;
  int i;
  for (i = 0; i < N; ++i) {
    if (etalon[i] == a) ia = i;
    if (etalon[i] == b) ib = i;
    if (ia >= 0 && ib >= 0) break;
  }
  return ia < ib;
}

int main() {
  int i, j;

  print_array("Original", from, N);
  insertion_sort(from, N, less);
  print_array("Converted", from, N);
  print_array("Etalon", etalon, N);

  return 0;
}

Запускаем:

 Original: 8 1 4 2 5 6 9 7 
Converted: 1 5 7 4 2 9 8 6 
   Etalon: 1 5 7 4 2 9 8 6 

Вроде работает.

Теперь что со сложностью. Принято считать, что сортировка вставками - это O(N^2) для худшего случая. Так как для сравнения элементов нам приходится искать линейно по эталонной последовательности на каждом шаге, то это еще O(N). В этоге: O(N^3).

Как вариант ускорения, можно изначально сделать отсортированную по значениям копию эталонной последовательности, и хранить не только значение, но его индекс. В этом случае поиск элемента будет уже занимать не O(N), а O(log(N)), и общая сложность будет O(log(N)*N^2).

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

Указание на эти два факта лично я счел бы на однозначно достаточный ответ.