배열 섞기

목표: 배열의 내용을 무작위로 재배열한다.

카드 게임을 만든다고 가정해 보자. 카드 덱을 Card 객체의 배열로 표현할 수 있으며, 덱을 섞는다는 것은 배열 내 객체의 순서를 바꾸는 것을 의미한다. (정렬의 반대 개념이다.)

스위프트에서 이를 구현하는 간단한 방법은 다음과 같다:

extension Array {
  public mutating func shuffle() {
    var temp = [Element]()
    while !isEmpty {
      let i = random(count)
      let obj = remove(at: i)
      temp.append(obj)
    }
    self = temp
  }
}

이 코드를 플레이그라운드에 복사한 후 다음과 같이 테스트할 수 있다:

var list = [ "a", "b", "c", "d", "e", "f", "g" ]
list.shuffle()
list.shuffle()
list.shuffle()

이 코드를 실행하면 배열의 객체들이 세 가지 다른 순서로 재배열된 것을 확인할 수 있다. 이를 수학 용어로 순열이라고 부른다.

이 shuffle() 메서드는 원본 배열을 직접 수정하는 제자리(in-place) 방식으로 동작한다. 알고리즘은 빈 배열 temp를 생성한 후, 원본 배열에서 무작위로 요소를 선택해 temp에 추가한다. 이 과정을 원본 배열이 빌 때까지 반복한 후, temp 배열을 다시 원본 배열로 복사한다.

이 코드는 정상적으로 동작하지만 효율적이지 않다. 배열에서 요소를 제거하는 작업은 **O(n)**의 시간 복잡도를 가지며, 이를 n번 반복하므로 전체 알고리즘의 시간 복잡도는 **O(n^2)**이 된다. 더 효율적인 방법이 존재한다!

Fisher-Yates / Knuth 셔플

다음은 훨씬 개선된 셔플 알고리즘이다:

extension Array {
  public mutating func shuffle() {
    for i in stride(from: count - 1, through: 1, by: -1) {
      let j = Int.random(in: 0...i)
      if i != j {
        swap(&self[i], &self[j])
      }
    }
  }
}

이 알고리즘도 무작위로 객체를 선택한다. 기존의 단순한 버전에서는 셔플된 객체와 아직 처리되지 않은 객체를 구분하기 위해 새로운 임시 배열에 객체를 넣었다. 그러나 이 개선된 알고리즘에서는 셔플된 객체를 원본 배열의 끝으로 이동시킨다.

예제를 통해 자세히 살펴보자. 다음과 같은 배열이 있다고 가정하자:

[ "a", "b", "c", "d", "e", "f", "g" ]

루프는 배열의 끝에서 시작해 처음으로 거꾸로 진행한다. 첫 번째 무작위 숫자는 배열 전체에서 어떤 요소든 선택할 수 있다. 예를 들어 2가 반환되었다고 하자. 이는 "c"의 인덱스다. "c"와 "g"를 교환해 "c"를 끝으로 이동시킨다:

[ "a", "b", "g", "d", "e", "f" | "c" ]
             *                    *

이제 배열은 | 기호로 표시된 두 영역으로 나뉜다. 기호 오른쪽은 이미 셔플된 영역이다.

다음 무작위 숫자는 0...6 범위에서 선택되므로 [ "a", "b", "g", "d", "e", "f" ] 영역에서만 선택된다. 이미 처리된 "c"는 다시 선택되지 않는다.

무작위 숫자 생성기가 0을 선택했다고 가정하자. 이는 "a"의 인덱스다. "a"와 셔플되지 않은 부분의 마지막 요소인 "f"를 교환하면 배열은 다음과 같이 된다:

[ "f", "b", "g", "d", "e" | "a", "c" ]
   *                         *

다음 무작위 숫자는 [ "f", "b", "g", "d", "e" ] 영역에서 선택된다. 예를 들어 3이 선택되었다고 하자. "d"와 "e"를 교환한다:

[ "f", "b", "g", "e" | "d", "a", "c" ]
                  *     *

이 과정은 왼쪽 영역에 하나의 요소만 남을 때까지 반복된다. 예를 들어:

[ "b" | "e", "f", "g", "d", "a", "c" ]

"b"와 교환할 요소가 더 이상 없으므로 작업이 완료된다.

이 알고리즘은 각 배열 요소를 한 번만 처리하므로 O(n) 시간 복잡도를 보장한다. 이는 가능한 가장 빠른 속도다!

새로운 배열을 섞어서 생성하기

0부터 n-1까지의 값을 무작위 순서로 포함하는 새로운 배열 인스턴스를 생성할 때 유용한 알고리즘의 약간 변형된 버전이 있다.

다음은 해당 코드다:

public func shuffledArray(_ n: Int) -> [Int] {
  var a = [Int](repeating: 0, count: n)
  for i in 0..<n {
    let j = Int.random(in: 0...i)
    // 위키피디아의 Fisher-Yates 셔플 의사 코드를 구현할 때, i != j인지 확인한다
    a[i] = a[j]
    a[j] = i
  }
  return a
}

이를 사용하는 방법은 다음과 같다:

let numbers = shuffledArray(10)

이 코드는 [3, 0, 9, 1, 8, 5, 2, 6, 7, 4]와 같은 결과를 반환한다. 보다시피, 0부터 10까지의 모든 숫자가 리스트에 있지만 순서가 섞여 있다. 당연히 직접 시도해보면 숫자의 순서가 달라질 것이다.

shuffledArray() 함수는 먼저 n개의 0으로 구성된 새로운 배열을 생성한다. 그런 다음 n번 반복하며 각 단계에서 시퀀스의 다음 숫자를 배열의 무작위 위치에 추가한다. 이때, 다음 숫자로 인해 이전 숫자가 덮어쓰여지지 않도록 먼저 이전 숫자를 옮기는 것이 핵심이다!

이 함수의 경우, j ≠ i인지 확인하는 조건은 초기화되지 않은 배열 값에 접근하는 데 문제가 없고, 비교보다 할당이 더 저렴한 언어에서는 생략할 수 있다. 위키피디아에서 이를 확인할 수 있다. 또한 확인 로직을 제거하면 성능이 최적화된다.

이 알고리즘은 상당히 영리하므로, 종이 위에서나 플레이그라운드에서 직접 예제를 따라가 보는 것을 추천한다. (힌트: 다시 한번 배열을 두 영역으로 나눈다.)

함께 보기

이 Swift 구현은 위키피디아 문서의 의사 코드를 기반으로 작성했다.

Mike Bostock은 이 알고리즘을 시각적으로 잘 표현한 자료를 제공한다.

Swift Algorithm Club을 위해 Matthijs Hollemans가 작성