Shuffle 알고리즘(Knuth Shuffle)

이번에 알아볼 알고리즘은, 임의의 List를 무작위로 섞는 알고리즘입니다.

 

음악을 듣거나 하실때 무작위재생 과 같은 기능이 위 알고리즘을 사용한다고 보실 수 있습니다 :)

 

Knuth Shuffle 알고리즘은 list의 한쪽부터 차례대로 랜덤한 위치에 Element를 Swap하는 방식으로

 

List를 무작위로 만들어줍니다. 다음 그림을 보시면 이해가 쉽습니다.

 

해당 알고리즘의 Sequence를 살펴보면,

 

N-1번의 반복작업이 필요한 것을 알 수 있습니다.(List의 Element가 1개 남으면 진행 불필요)

 

때문에 해당 알고리즘의 시간복잡도를 살펴보면

 

T(n) = T(n-1) + Θ(n)  (Θ(n) = Random Index를 추출할 때 걸리는 시간)

 

이 점화식을 풀어주면, T(n) = O(n)의 시간복잡도를 갖는 알고리즘이라고 할수있습니다.

 

매번 Python의 random 패키지의 random.shuffle을 활용하였는데, 이러한 방법이 숨어있었네요.

 

Python Code로 구현된 Knuth Shuffle 알고리즘 소스코드입니다 :)

import random

#List와 Index를 받아서 값을 Swap해주는 함수를 정의합니다.
def swap(target_list, start_index, end_index):
    temp = target_list[start_index]
    target_list[start_index] = target_list[end_index]
    target_list[end_index] = temp


def shuffle(DT_list):
    #마지막 부터 Index가 1일때까지 Swap을 진행합니다.
    for i in range(len(DT_list)-1):
        #선택된 Index를 제외한 나머지 부분 배열에서
        #Random하게 Index를 선택합니다.
        change_index = random.randint(0, (len(DT_list)-1)-i)
        #Random하게 선별된 Index와 값을 Swap
        swap(DT_list, (len(DT_list)-1)-i, change_index)
    return DT_list
        
#정렬된 List를 생성합니다.
test_list = [i for i in range(10)]
 ==> [0,1,2,3,4,5,6,7,8,9]

#Random하게 Shuffle된 List를 반환합니다.
shuffle(test_list)
 ==> [7, 1, 0, 6, 3, 2, 9, 4, 5, 8]