Алгоритм Пірсона – перестановка з мінімальною кількістю переставлень

Повне пояснення

Коротке пояснення

Алгоритм Пірсона визначає, скільки мінімальних перестановок треба виконати, щоб відсортувати масив. Він розглядає перестановку як набір циклів і для кожного циклу додає довжину –1 до загальної кількості перестановок.

Аналогія

Уявіть, що кожен елемент – це людина у колі, яка тримає ключ. Кожен ключ повинен потрапити до власника; людина, що тримає неправильний ключ, передає його далі. Коли коло розбивається на підкола (цикли), кількість передач – це довжина –1.

Коли застосовувати

• Вхід – масив цілих чисел, що є перестановкою від 1 до n.
• Необхідно знайти мінімальну кількість обмінів парних елементів.
• Потрібно, щоб після перестановок масив став відсортованим за зростанням.
• Алгоритм працює швидко навіть для великих n (до 10⁶).
• Підходить, коли обмін елементів – дорогий операційний витрат.

Кроки алгоритму

1. Створити масив‑помічник, що відображає поточну позицію кожного числа.
2. Ініціалізувати змінну swaps нульом.
3. Для кожного елемента, якщо він ще не в своєму місці:
   • Запустити цикл, слідкуючи за послідовністю елементів у цьому циклі.
   • Підрахувати довжину циклу len.
   • Додати len-1 до swaps.
4. Повернути значення swaps.

Візуальна інтуїція (текстова)

Масив: [4, 3, 2, 1]
Позиції: 0→3, 1→2, 2→1, 3→0
Цикли: (0 3) і (1 2)
Довжини: 2, 2 → перестановок: (2-1)+(2-1)=2

Складність

Часова складність: O(n) – кожен елемент обробляється один раз. Пам’ятна складність: O(n) – потрібен масив‑помічник довжини n.

Код (js)

// Функція, що повертає мінімальну кількість перестановок для сортування масиву
function minSwapsToSort(arr) {
  const n = arr.length;
  // Копія масиву з індексами, щоб знати поточну позицію кожного елемента
  const indexMap = new Array(n);
  for (let i = 0; i < n; i++) {
    indexMap[arr[i] - 1] = i; // елемент x має бути на позиції x-1
  }

  let swaps = 0; // загальна кількість перестановок
  const visited = new Array(n).fill(false); // чи вже оброблений елемент

  for (let i = 0; i < n; i++) {
    // Якщо елемент вже на своєму місці або вже входить до обробленого циклу
    if (visited[i] || indexMap[i] === i) continue;

    let cycleSize = 0;
    let j = i;
    // Перебираємо елементи циклу
    while (!visited[j]) {
      visited[j] = true;
      j = indexMap[j];
      cycleSize++;
    }

    // Для циклу довжини cycleSize потрібні (cycleSize - 1) перестановок
    if (cycleSize > 0) swaps += cycleSize - 1;
  }

  return swaps;
}

// Тестовий приклад
console.log(minSwapsToSort([4, 3, 2, 1])); // очікуваний результат: 2

Типові помилки і поради

1. Неправильне відображення позицій – пам’ятайте, що елемент x повинен бути на індексі x-1.
2. Відсутність масиву visited – без нього цикл може повторюватися нескінченно.
3. Використання forEach замість звичайного циклу – це може призвести до неправильних індексів.
4. Забудьте про випадок, коли елемент вже на місці – це зменшує кількість обчислень.
5. Оптимізація – можна зменшити пам’ять, використовуючи маркер -1 у масиві замість окремого visited.

Перевір себе

1. Якщо масив вже відсортований, скільки перестановок поверне функція?
2. Як зміниться результат, якщо масив містить дублікатів (не перестановку)?