피셔-예이츠(Fisher-Yates) 알고리즘은 배열 요소들의 무작위 순열(random permutation)을 생성하는 알고리즘입니다. 즉, 배열의 모든 요소를 무작위로 섞는(shuffle) 데 사용됩니다. 이 알고리즘은 편향되지 않았기(unbiased) 때문에 가능한 모든 순열이 동일한 확률로 나타난다는 것이 큰 장점입니다.
아래는 C++로 배열 셔플링을 위한 피셔-예이츠 알고리즘을 구현한 프로그램입니다.
예제 코드
#include <iostream>
#include <stdlib.h>
using namespace std;
int main() {
int n;
cout << "Enter the array size: "<<endl;
cin >> n;
int arr[n], arr1[n], index_arr[n];
int index;
cout << "Enter the array elements: "<<endl;
for (int i = 0; i < n; i++)
cin >> arr[i];
for (int i = 0; i < n; i++)
index_arr[i] = 0;
for (int i = 0; i < n; i++) {
do {
index = rand() % n;
}
while (index_arr[index] != 0);
index_arr[index] = 1;
arr1[i] = arr[index];
}
cout<<"The shuffled array is: ";
for (int i = 0; i < n; i++)
cout << arr1[i] << " ";
return 0;
}실행 결과
위 프로그램의 실행 결과는 다음과 같습니다.
Enter the array size: 10 Enter the array elements: 1 2 3 4 5 6 7 8 9 10 The shuffled array is: 4 7 8 6 3 10 2 1 9 5
코드 단계별 설명
위 프로그램에서는 먼저 사용자로부터 배열의 크기와 배열 요소들을 입력받습니다. 해당 부분의 코드는 다음과 같습니다.
cout << "Enter the array size: "<<endl; cin >> n; int arr[n], arr1[n], index_arr[n]; int index; cout << "Enter the array elements: "<<endl; for (int i = 0; i < n; i++) cin >> arr[i];
여기서 arr[]은 원본 배열, arr1[]은 셔플 결과를 저장할 배열, index_arr[]는 각 인덱스가 이미 사용되었는지 여부를 추적하는 보조 배열입니다.
배열 입력이 완료되면 index_arr[]의 모든 값을 0으로 초기화합니다. 이후 rand() 함수를 이용해 무작위 인덱스를 뽑고, 아직 사용되지 않은 인덱스라면 해당 위치의 값을 arr1[]에 저장합니다. 이 과정은 다음 코드 조각에서 확인할 수 있습니다.
for (int i = 0; i < n; i++) {
do {
index = rand() % n;
}
while (index_arr[index] != 0);
index_arr[index] = 1;
arr1[i] = arr[index];
}do-while 루프는 이미 선택된 인덱스가 중복해서 뽑히지 않도록 반복 검사를 수행하며, 새 인덱스가 선택되면 index_arr[index]를 1로 설정하여 해당 인덱스를 '사용됨' 상태로 표시합니다.
마지막으로 셔플이 완료된 배열을 화면에 출력합니다.
cout<<"The shuffled array is: "; for (int i = 0; i < n; i++) cout << arr1[i] << " ";
참고 사항
rand() 함수를 사용하기 전에 srand(time(NULL))를 호출하면 프로그램을 실행할 때마다 서로 다른 시드(seed)가 적용되어 더욱 다양한 셔플 결과를 얻을 수 있습니다. 또한 이 방식은 매번 빈 인덱스를 찾을 때까지 재시도하므로 최악의 경우 성능이 저하될 수 있으며, 실무에서는 배열 끝부터 시작해 남은 구간 내에서만 교환하는 표준 피셔-예이츠 방식(O(n))을 사용하는 것이 더 효율적입니다.