Fisher-Yates algorithm과 Knuth Shuffle algorithm 의 차이

리눅스에서 C를 사용한 간단한 게임을 만들고 있는데요, 카드덱을 섞을 일이 있어서 섞는 알고리즘을 지피티쟝이 알려줌

 

근데 Fisher-Yates algorithm이랑 Knuth Shuffle algorithm 이렇게 두가지가 있더라고요? 

제가 썼던건 knuth shuffle인데 지피티한테 효율적으로 바꿔달라 하니까 fisher yates로 바꾸길래 어떤 차이가 있나 싶어서 알아봤습니다.

 

Fisher-Yates Algorithm 의 역사

Fisher-Yates 알고리즘은 1938년 Ronald A. Fisher와 Frank Yates가 고안한 알고리즘입니다.

이 알고리즘은 원래 통계학에서 무작위로 섞은 샘플을 만들기 위해 개발되었는데, 나중에 컴퓨터 분야에서 배열을 무작위로 섞는데 사용되었다고 한다.

 

처음 컴퓨터 분야에서 사용되기 시작한건 1964년이다. 초기 버전에는 배열의 각 요소를 무작위로 선택할때 주사위를 이용했지만, 나중엔 난수 생성기를 사용해서 구현되었다고 한다. 지금은 아주 빠르고 효율적으로 구현할수 있다. 

 

사실 이건 굳이 알 필요는 없는데... 제가 궁금함

이름이 너무 귀엽고 찰져서 왜 fisher 지? 사람 이름이 fisher인가? 싶어서 알아봤어요

 

근데 진짜 사람 이름이었음... 죄송

 

Fisher-Yates Algorithm 이란?

이 알고리즘은

1. 섞을 배열의 마지막 요소부터 시작하여, 배열의 첫 요소까지 반복합니다.
2. 현재 위치에서 이전 위치까지의 범위에서 무작위로 하나의 요소를 선택합니다.
3. 현재 위치와 선택된 위치의 요소를 교환합니다.
4. 이전 위치로 이동하여 반복을 계속합니다.
   
   

이런식으로 작동된다.

 

모든 요소가 균등하게 무작위로 선택되기 때문에, 섞는 효과가 높다. 

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

 

Fisher-Yates Algorithm 과 Knuth Shuffle Algorithm의 차이

Fisher-Yates:

import random

def fisher_yates_shuffle(arr):
    n = len(arr)
    for i in range(n-1, 0, -1):
        j = random.randint(0, i)
        arr[i], arr[j] = arr[j], arr[i]
    return arr

# 예시
arr = [1, 2, 3, 4, 5]
print(fisher_yates_shuffle(arr))

 

Knuth Shuffle:

import random

def knuth_shuffle(arr):
    n = len(arr)
    for i in range(n-1):
        j = random.randint(i, n-1)
        arr[i], arr[j] = arr[j], arr[i]
    return arr

# 예시
arr = [1, 2, 3, 4, 5]
print(knuth_shuffle(arr))

 

무슨 차이가 있냐면 

Fisher-Yates 알고리즘	배열의 뒤에서부터 앞으로 이동하면서 요소를 선택하여 섞음	O(n)
Knuth Shuffle 알고리즘	배열의 앞에서부터 뒤로 이동하면서 요소를 선택하여 섞음	O(n)

이런 차이가 있다. 

Fisher yates는 배열의 뒤에서부터 앞으로 이동하고 knuth shuffle은 앞에서부터 뒤로 이동한다. 

 

그래서 그냥 차이는 앞에서부터 하냐 뒤에서부터 하냐의 차인데 지피티는 계속 내 knuth shuffle 알고리즘을 fisher yates 로 바꾼다. 왜그러는지 모르겠다;;