C++ 배열 요소 무작위로 섞기(셔플) 알고리즘 구현하기

이 알고리즘은 배열을 입력받아 배열의 내용을 무작위로 섞는(shuffle) 기능을 수행합니다. 즉, 배열 요소들의 랜덤 순열(random permutation)을 생성하는 것이 목적입니다.

이 문제를 해결하는 방법은 배열의 마지막 인덱스부터 시작하여, 0부터 현재 인덱스 사이에서 무작위로 선택한 인덱스의 요소와 서로 교환(swap)하는 것입니다. 이 방식은 널리 알려진 피셔-예이츠 셔플(Fisher-Yates Shuffle) 알고리즘과 동일하며, 모든 순열이 동일한 확률로 나타나도록 보장하는 효율적인 방법입니다.

입력과 출력

입력:
정수 배열: {1, 2, 3, 4, 5, 6, 7, 8}
출력:
섞인 배열 내용: 3 4 7 2 6 1 5 8 (실행할 때마다 결과는 달라질 수 있음)

알고리즘

randomArr(array, n)

입력: 배열과 요소의 개수 n

출력: 배열의 내용을 무작위로 섞음

Begin
   for i := n – 1 down to 1, do
      j := 0부터 i 사이의 무작위 숫자
      swap arr[i] and arr[j]
   done
End

핵심 아이디어는 다음과 같습니다. 뒤쪽 인덱스부터 앞으로 이동하면서 각 위치 i에 대해, 0부터 i까지 범위에서 무작위 인덱스 j를 하나 뽑은 뒤 arr[i]와 arr[j]의 값을 맞바꿉니다. 이미 확정된 뒤쪽 영역은 다시 건드리지 않기 때문에, 모든 가능한 순열이 균등한 확률로 생성됩니다.

예제 코드

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void display(int array[], int n) {
    for (int i = 0; i < n; i++)
        cout << array[i] << " ";
}

void randomArr(int arr[], int n) {          // 배열 요소를 무작위로 섞는 함수
    srand(time(NULL));                      // 시간을 이용해 매번 다른 시드 값 설정
    for (int i = n - 1; i > 0; i--) {
        int j = rand() % (i + 1);           // 0부터 i 사이에서 무작위 인덱스 선택
        swap(arr[i], arr[j]);               // 현재 요소와 j번째 위치의 요소를 교환
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = 8;
    randomArr(arr, n);
    display(arr, n);
}

실행 결과

4 7 8 2 6 3 5 1

프로그램을 실행할 때마다 srand(time(NULL))을 통해 새로운 시드 값이 설정되므로, 위와 같이 실행 결과는 매번 달라집니다. 이 알고리즘의 시간 복잡도는 O(n)으로, 배열의 크기에 비례하여 한 번씩만 순회하면 되기 때문에 매우 효율적입니다.