[Algorithm] Shuffle Sort

Shuffle Sort 에 대해 알아볼 것이다. 이름에 Sort가 들어가서 단순히 '정렬'문제인가 착각할 수 있는데 정렬을 이용하여 uniformly random한 값을 얻는 방법을 의미한다.

 

Shuffle Sort

Shuffle의 개념

셔플은 말 그대로 섞는 것이다. 입력 데이터의 순서를 임의로 섞어야 한다.

N = [1,2,3] 이 주어졌으면, 나올 수 있는 순서는 어떤 것이 있을까?
=> [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]로 총 6가지이다. 

일반적으로 N개의 데이터를 입력 받으면 N! 개의 경우의 수가 발생한다. 그리고 이 중 하나를 얻을 확률은 1/N!이다. 

가장 쉽게 Shuffle하여 uniformly random한 결과를 얻는 방법은 모든 경우의 수를 얻고(brute-force로 permutation 발생) 이 중 하나를 랜덤으로 뽑는 것이다. 하지만, 이 방식은 N!개의 경우의 수를 발생시켜야하기 때문에 매우 비효율적이다. 

그래서 우리는 Shuffle을 Sort를 이용해 해보자는 아이디어를 얻었고 이것이 Shuffle Sort이다. 

 

Shuffle Sort 

Sort를 직접 활용한다.
Uniformly random한 분포로부터 난수를 발생시키면, shuffle 결과도 uniformly random한다.

import random

def shuffleSort(a):
	r = []
    for _ in range(len(a)):
    	r.append(random.random())
    return [i for i in sorted(zip(a, r) , key = lambda x:x[1])]

난수 발생에 상수시간이 소요된다고 하면 shuffle sort의 성능은 정렬의 성능과 비례하기 때문에 ~NlogN 시간이 소요된다.

 

Knuth's Shuffle

insertion sort의 방식과 유사하다. 이미 uniformly random된 부분에 새로운 데이터를 uniformly random한 위치로 swap하는 것이다. 

import random

def knuthShuffle(a):
	for i in range(1, len(a)): # ~N
    	j = random.randint(0, i) # ~1
        a[i], a[j] = a[j], a[i] # ~1

insertion sort와는 다르게 한 iteration에서 swap을 한 번만 진행하고, shuffle이기 때문에 결과값에 대한 비교는 하지 않아도 된다.

 

Shuffle Sort 사용 예제

1. MS Window 기본 브라우저 선택 화면(실제 사례)
EU에서 여러 웹 브라우저 개발사에게 공정한 기회를 주기 위해 웹 브라우저 목록을 random shuffle하게 제공하기로 했고 이를 위해 shuffle sort를 사용했다. 

2. 여러 게임
random sequence를 발생시켜야하는 경우 shuffle 기능을 사용하면 효율적으로 구현할 수 있다.

3.SW 테스트
다양한 입력 데이터를 발생시킬 때 랜덤한 테스트 결과를 만든다.