Четность количества свопов алгоритмов сортировки на основе свопов

Question

Если у меня есть перестановка целых чисел от 0 до n-1, и я хочу отсортировать перестановку в порядке возрастания, правда ли, что независимо от того, какой метод сортировки на основе свопа является четность количества свопов, которые потребуется для сортировки, будет одинаковым для всех основанных на свопах методов сортировки?

Например, рассмотрим своп приведенный ниже метод сортировки, написанный на C ++:

(ПРИМЕЧАНИЕ: pos[i] сохраняет текущий индекс (на основе 0) элемента 'i' в списке)

int cnt = 0; // stores the number of operations
  for (int i = 0; i < n; i++) {
    if (pos[i] != i) {
      cnt++;
      int temp = a[i];
      int temp_pos = pos[i];
      swap(a[i], a[pos[i]]);
      pos[i] = i;
      pos[temp] = temp_pos;
    }
  }

Будут ли алгоритмы сортировки на основе , такие как приведенный выше, иметь такую ​​же четность количества свопов, необходимых для сортировки, по сравнению с другими методами сортировки на основе свопа, когда они выполняются с той же перестановкой целых чисел из От 0 до n-1?

Answer 1

Да, это правда. Набросок доказательства выглядит примерно так:

инверсия в последовательности элементов - это любая пара элементов, которые не отсортированы должным образом: то есть a[i] > a[j] для некоторых i < j. Полностью отсортированный массив не имеет инверсий. Замена любых двух элементов меняет общее количество инверсий на нечетное число (доказательство этого оставлено в качестве упражнения для читателя). Следовательно, если массив изначально имеет нечетное количество инверсий, нечетное количество перестановок должно быть выполнено для его сортировки; и если он начинается с четного числа инверсий, потребуется четное число перестановок.