Inside-Out Fisher–Yates

Inside-Out Fisher–Yates

Inside-Out Fisher–Yates 은 일반적인 피셔 예이츠 ( Fisher Yates ) 셔플의 변형 버전이다.

핵심 아이디어는 새로운 배열을 만들면서 동시에 섞인 상태를 채워 넣는 것이다.

 

 

 

동작 과정 

• 길이가 같은 새 배열을 준비한다.
• i = 0 부터 n-1 까지 순회하면서
• 랜덤 인덱스 j 를 0 ~ i 범위에서 뽑는다.
• 새 배열의 i 에 원본 배열의 i 를 넣는다.
• 만약 j != i 라면, 새 배열의 i 대신에 j 위치의 원소와 교체한다.
• 이렇게 하면 새 배열이 완전히 무작위로 섞인다.

 

 

 

의사코드 ( PseudoCode ) 표현

for i = 0 → (배열의 마지막 인덱스)까지 반복한다
    0부터 i까지 범위에서 무작위 인덱스 j를 선택한다

    만약 j ≠ i 이면
    newArray[i] ← newArray[j]   // 이전 값 복사
    newArray[j] ← original[i]       // 현재 값을 무작위 위치에 배치한다

 

 

 

▼C# 예제 코드

using System;

class Program
{
    static void Main()
    {
        int[] original = {1, 2, 3, 4, 5};
        int[] shuffled = new int[original.Length];
        Random rand = new Random();

        for (int i = 0; i < original.Length; i++)
        {
            int j = rand.Next(i + 1); // 0 ~ i 사이에서 랜덤
            if (j != i)
                shuffled[i] = shuffled[j]; // 기존 값 복사
            shuffled[j] = original[i];     // 현재 값 배치
        }

        Console.WriteLine("Original: " + string.Join(", ", original));
        Console.WriteLine("Shuffled: " + string.Join(", ", shuffled));
    }
}

 

 

특징

• 원본 배열을 그대로 보존할 수 있다.
• 결과 배열을 한 번의 패스 (O(n))로 만들어낸다.
• 인덱스 i 를 차례대로 채워나가면서 무작위로 섞이는 효과를 만든다.

 

 

 

장점

• 원본 배열을 바꾸지 않고 섞을 수 있다.
• 한 번만 순휘하므로 빠르다 (O(n))

 

단점

• 새 배열이 필요하므로 추가 메모리 O(n) 사용한다.
• 원본 배열 자체를 직접 섞고 싶다면 Fisher Yates 가 더 효율적이다.