순열 정렬 알고리즘 (Permutation sort algorithm)

서론

오늘부터 정렬 알고리즘을 공부해볼 것이다. 그 중에서 가장 기본적인 순열 정렬(Permutation Sort)를 먼저 학습하려고 한다. 가장 기본적이라고 언급한 이유는, brute-force 기반이기 때문이다. 모든 케이스를 다 나열해보고, 알맞는 하나를 찾아가는 알고리즘이다.

문제 푸는 아이디어

[3,2,1] 을 오름차순으로 정렬하려고 한다. 아주 무식한 방법(brute-force)로 정렬한다고 해보자. 그렇다면 3,2,1 이라는 3개의 원소를 가지고, 만들 수 있는 모든 케이스를 만들고, 각각의 케이스가 오름차순 정렬되어 있는지 확인하는 것이다. 이것이 brute-force 기반 정렬인, 순열 정렬이다.

 

정리하자면, 이 문제는 두가지 Step 으로 나뉜다.

1. 순열 생성
2. 정렬 여부 확인

순열(順列) 이란?

순열은, 순서를 부여하며 나열하는 수학적 개념이다. 이를테면, 1,2,3,4,5 라는 5개 숫자를 임의의 순서를 부여하며 나열하는 것이다. 5개의 slot 을 두고, 하나씩 배치한다고 했을때, 5x4x3x2x1 (5!) 개의 연산을 가진다. 이처럼 순열의 결과는 factorial 이다.

정렬 여부 확인 알고리즘

정렬 여부를 확인하는 알고리즘은 무엇을 사용할 것인가?

배열 [a_1, a_2, a_3, ..., a_n]이 있을 때, 다음과 같은 방식으로 배열이 정렬되었는지 확인할 수 있다.

• a_1 ≤ a_2 ≤ a_3 ≤...≤ a_n

이 연산은 얼마나 소요되는가?

n 개의 요소에 대해서, n-1번 비교작업을 거쳐야 한다. 1,2 비교 / 2,3 비교 / 3,4 비교 / … / n-1,n 비교가 필요하기 때문이다.

예시

[3,2,1] 을 정렬한다고 하자.

 

1. 순열 생성

만들 수 있는 모든 케이스는 아래와 같다.

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

순열 가지수를 계산하면, 3! = 6 가지가 맞다.

 

2. 정렬 여부 확인

각 케이스별로, 2번 비교연산을 하면 된다. 1,2번째 비교 / 2,3번째 비교만 있으면 된다.

즉 전체적인 연산횟수는 3! * (3-1) = 6x2 이다.

시간복잡도

시간복잡도를 일반화하여 표현해보자. 연산횟수를 worst, best 두가지로 표현해본다.

세가지 모두 순열 생성을 해야함은 동일하다. 정렬 여부 확인이 얼마나 빨리 끝나야에 따라서, Worst, Best 가 정해진다.

• Worst
  • 오름차순 정렬된 요소가 순열의 마지막에 존재하는 케이스이다.
  • 순열 생성이 n!, 정렬여부 확인이 n-1 이다. 즉 총 연산횟수는 n! * (n-1) 이다.
• Best
  • 오름차순 정렬된 요소가 순열의 첫번째에 존재하는 케이스이다.
  • 순열 생성이 n!, 정렬여부 확인이 1 이다. 즉 총 연산횟수는 n! * 1 이다.

일반적으로 알고리즘의 BIg O notation 은 worst case를 따르므로, 순열 정렬의 시간복잡도는 O(n*n!) 이다.

공간복잡도

공간 복잡도는 알고리즘 실행에 필요한 메모리 사용 양이다.

n! 개의 배열이 필요하고, 각 배열은 n개의 요소를 가진다.

그러므로 순열 정렬의 공간복잡도는 O(n!*n) 이다.

안정성

알고리즘의 안정성은 동일한 키를 가진 요소의 순서가 정렬 후에 유지되는지 여부이다.

순열 정렬 알고리즘은 임의의 n! 개의 배열을 생성하고, 순차적으로 순회하면서 정렬 여부를 확인한다. 그러므로 기존의 순서를 100% 보장한다고 볼 수 없다. 즉 순열 정렬은 안정적인 정렬 알고리즘이 아니다.

예시 코드

함수 자체는 복잡하지만, 순열 생성, 정렬 여부 확인 2단계로 생각하면 매우 간단하다. 아래 예시 코드를 첨부한다.

https://github.com/euijinkk/algorithm/blob/main/sort/permutation-sort.js

// 1. 순열 생성
function permute(arr, _k) {
  const k = _k ?? arr.length;
  const result = [];

  function recursive(alreadySelected) {
    if (alreadySelected.size === k) {
      result.push(Array.from(alreadySelected));
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      if (alreadySelected.has(arr[i]) === true) {
        continue;
      }
      alreadySelected.add(arr[i]);
      recursive(alreadySelected);
      alreadySelected.delete(arr[i]);
      continue;
    }
  }

  recursive(new Set([]));

  return result;
}

// 2. 정렬 여부 확인
function isAscending(arr) {
  return arr.every((_, i) => {
    if (i === arr.length - 1) {
      return true;
    }
    return arr[i] <= arr[i + 1];
  });
}

function permutationSort(arr) {
  const permutations = permute(arr);

  return permutations.find(isAscending);
}

마치며

정렬을 공부하며, 가장 기본적인 순열 정렬을 알아보았다. 이는 실제 코드에 쓸 수는 없다. 시간 복잡도가 O(n!*n) 이기 때문에, n이 10만 넘어가도, 천만번 이상의 연산이 필요하여 성능이 매우 느리다. 하지만, brute-force 의 기본 컨셉, 재귀 등 학습 관점에서 괜찮은 예제라고 생각한다.