C# - 피셔 예이츠 셔플 (Fisher Yates Shuffle)

코딩테스트던 게임개발이던 프로그래밍을 할 때 랜덤하게 섞는 기능은 자주 사용하게 된다.

피셔 예이츠는 난수 기반 섞기의 대표적인 고전 알고리즘이다.

구현 방법은 매우 간단하다.

 

public static void FisherYatesShuffle(int[] inputArr)
{
    Random random = new Random(); //

    for (int i = inputArr.Length - 1; i > 0; i--)
    {
        int j = random.Next(0, i + 1);

        int temp = inputArr[i];
        inputArr [i] = inputArr[j];
        inputArr [j] = temp;
    }
}

 

배열을 뒤에서부터 하나씩 인덱스를 순회하면서, 랜덤한 인덱스와 교환해주는 매우 간단한 구조다.

 

스왑 부분은 참고로

(arr[i], arr[j]) = (arr[j], arr[i]);

 

이런 형태로 간단하게 표현할 수도 있다.

 

시간복잡도	O(n) - 한 번씩만 순회
공간 복잡도	O(1) - 추가 메모리 거의 없음
균등성	완전한 Uniform Random Distribution