Elementary Sorts(4) : Shuffling

How to shuffle an array

 

Shuffle sort

• 랜덤하게 생성한 실수를 부여하고 이를 정렬하는 방식으로 shuffle을 할 수 있습니다.

 

Knuth shuffle

• 하지만 선형 시간을 소요하면서 빠르게 shuffle할 수 있는 방법이 있습니다.
• 배열을 순서대로 탐색하면서, i 번째 이전의 정수값들을 랜덤하게 하나 골라서 i 번째 원소와 교환하는 것입니다.

import random

n = len(a)
for i in range(n):
	r = random.randint(0,i-1)
    a[i],a[r] = a[r],a[i]

• 파이썬 코드로 구현하면 위와 같습니다.

 

War story (online poker)

• 간단해 보이는 shuffle 함수에도 네 개나 되는 버그가 존재한다고 하네요.
  52개의 카드 중 52번째가 제외되었다거나, 균일한 확률을 갖지 않는다거나 등등..
• 결론은 shuffle도 생각보다 쉬운 것은 아니다~

 

 

출처: Coursera, Algorithms, Part 1, Princeton University