Swift - Array shuffle()

Swfit의 Shuffle( )

"Use the shuffle() method to randomly reorder the elements of an array."

shuffle()은 배열의 순서를 랜덤화 하는 함수입니다.

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

WWDC2018 Generic을보다가 shuffle()이 어떻게 구현되었는지 언급이 되길래 정리하고자 합니다.

사용된 fisher yates shuffle 알고리즘은 오래된 알고리즘입니다.

위에서 shuffle()은 배열을 랜덤화 할때 사용하는 함수라고 했으니

array.shuffle()을 해주고 print를 찍어보면 잘 섞여서 나오는걸 확인할 수 있습니다.

위 print문이 어떻게 찍혔는지 과정을 살펴봅시다.

먼저 컬렉션의 첫 번째 요소에 대한 인덱스부터 시작합니다.

그런 다음 컬렉션의 다른 요소를 무작위로 선택하고 두 요소를 서로 바꿉니다.

여기서는 1과 7이 바뀌었네요.

다음 왼쪽 인덱스를 앞으로 이동합니다.

그래서 위에 보이는 Choose at Random의 인덱스가 5부터 시작됩니다.

다음은 2와 5가 바뀌었네요.

바뀐 인덱스부터 끝 사이(Choose at Random범위)에서 무작위로 하나를 선택하고, 그 원소들을 Swap합니다.

다음 왼쪽 인덱스를 앞으로 이동합니다.

여기서는 3이 9와 바뀌었네요.

다음 왼쪽 인덱스를 앞으로 이동합니다.

4와 6이 변경되고 이렇게 같은 동작을 쭉 반복합니다.

알고리즘은 매우 간단합니다. 

- linear , swap

WWDC동영상 : (https://developer.apple.com/videos/play/wwdc2018/406/)

공식문서 : (https://developer.apple.com/documentation/swift/array/2994753-shuffle)