THIS IS ELLIE

스위프트 데이터 구조와 알고리즘 책을 읽으며 알게 된 사실. 흔히 아는 퀵 정렬. 스위프트에서도 정렬 함수에 퀵 정렬이 사용된다. 그만큼 강력한 정렬이고 장점이 많다. 평균 시간복잡도는 O(nlogn)이다. 하지만 피봇 값에 따라 편향되게 분할될 가능성도 있어 최악의 경우 시간복잡도는 O(n^2)이다. 예를 들어 이미 정렬할 데이터가 정렬되어 있거나 역으로 정렬되어 있는 경우 피봇이 한쪽으로 치우쳐 N개의 원소를 피봇 기준으로 나누는 작업을 N번 실행하기 때문에 최악의 경우는 O(n^2)의 시간 복잡도를 가지기도 한다. 퀵 소트가 좋다고는 하지만 최악의 경우는 높은 성능을 기대하기도 어렵다. 이를 해결하기 위해서 개선된 방식으로는 피봇을 정하는 인덱스를 처음과 끝으로 고정시키지 않는다는 것이다. 그럼 이..

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문이 어떻게 찍혔는지 과정을 살펴봅시다.먼저 컬렉션의 첫 번째 요소에 대한 인덱스부터 시작합..