알고리즘) Fisher-Yates 알고리즘

Fisher-Yates 알고리즘

 

배열이나 리스트 같은 데이터 구조의 요소들을 무작위로 섞는 데 사용되는 알고리즘이다,

균등하게 분포된 무작위 배열을 생성하는 데 효율적이고 널리 사용된다.

단순하게 순차적으로 유지하면서 무작위로 선택된 이전 위치와 교환하는 방식으로 동작한다.

이를 통해 모든 가능한 순열이 동일한 확률로 생성된다.

 

가장 널리 쓰이는 셔플 알고리즘이다.

 

반응형

 

< 코드 >

using System;

class Program
{
    static void Main(string[] args)
    {
        int[] array = { 1, 2, 3, 4, 5 };

        // Fisher-Yates 알고리즘으로 배열 섞기
        FisherYatesShuffle(array);

        // 결과 출력
        Console.WriteLine(string.Join(", ", array));
    }

    static void FisherYatesShuffle(int[] array)
    {
        Random random = new Random(); // 난수 생성기
        int n = array.Length;

        for (int i = n - 1; i > 0; i--)
        {
            // 0부터 i까지의 무작위 인덱스 생성
            int j = random.Next(0, i + 1);

            // i와 j 위치의 값을 교환
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}

 

 

시간 복잡도는  O(n)이다.

각 요소를 한번만 처리하기 때문에 선형 시간 복잡도를 가진다.

무작위로 생성해야하는 순열이 많을수록 무작위성에 구현이 높다.

 

★★☆☆☆