*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

пятница, 2 апреля 2010 г.

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

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

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

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

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

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

10 комментариев:

  1. Тест

    #define N 9

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

    Уже не проходит из-за того, что значение "1" не уникально.

    Вывод:
    Original: 8 1 1 4 2 5 6 9 7
    Converted: 1 1 5 7 4 2 9 8 6
    Etalon: 1 5 7 4 2 9 8 6 1

    Тут надо как-то хитрее.

    ОтветитьУдалить
  2. Этот комментарий был удален автором.

    ОтветитьУдалить
  3. Что-то не могу засунуть код в комментарий
    Можно за n^2:

    1. for (i=1;i<n;i++) {
    2.   if (q[i]!=e[i]) {
    3.     for (j=i+1;j<n&&q[j]!=et[i];j++);
    4.     

    ОтветитьУдалить
  4. 4.     for(k=j;k>i;k--) {
    5.       tmp=q[j]; q[j]=q[j-1]; q[j-1]=tmp;
    6.     }
    7.   }
    8. }

    ОтветитьУдалить
  5. загадил я пост, простите меня...

    ОтветитьУдалить
  6. R-ride: Да, с повторяющимися ключали лажа вышла. Если они есть, то надо создавать новый алфавит, где все элементы исходного, включая повторяющиеся, буду отображаться на уникальные значения. По ним сортировать, и потом делать отображение назад.

    ОтветитьУдалить
  7. Nick: Ничего, сегодня блоггер глючит. Я почистил дупликаты.

    ОтветитьУдалить
  8. Можно до начала собственно сортировки определить для каждого элемента исходного вектора в какую позицию эталонного вектора он должен отобразиться (сложность вычисления этих значений в наивной реализации будет O(n^2)).
    Т.е. для исходного вектора получим вектор - некоторую перестановку чисел от 0 до n-1.
    Можно объединить исходный вектор и его вектор перестановки в вектор, хранящий pair[int,T] - пару позиции элемента в эталонном векторе и значение этого элемента.
    Тогда и функций less не нужна - pair будут сравниваться в первую очередь по позиции в эталонном векторе, что нам и надо.
    Конечно, не очень экономно в плане памяти, но будет работать как O(n^2).
    Можно еще подумать над (поискать) алгоритмом, являющийся модификацией какой-нибудь log(n)*n сортировки.

    ОтветитьУдалить
  9. Этот комментарий был удален автором.

    ОтветитьУдалить
  10. for (int fixpos=n-1; fixpos>0; fixpos--)
       for (int i=0; i<fixpos; i++)
          if (etalon[fixpos] == original[i])
             swap(original[i], original[i+1]);
    // Как то так. Не проверял ещё на компе.

    Алгоритм загоняет значения в конец по одному. После первой итерации главного цикла на своём месте будет стоять последний элемент. После второй итерации - предпоследний элемент будет содержать необходимое значение и т.д. Если не ошибаюсь сложность составляет:
    n+(n-1)+(n-2)+...+2+1 = (n+1)*n/2 => O(n^2)

    ОтветитьУдалить