Swift의 Sorting Algorithm은 무엇인가요?

[0Hooni]

No description provided.

[youn9k]

Swift의 sort와 sorted 메소드는 내부적으로 Time Sort Algorithm으로 구현되어있습니다.
Time Sort는 합병 정렬(Merge Sort)와 삽입 정렬(Insertion Sort)를 조합한 알고리즘으로 최선의 경우 O(n), 최악의 경우 O(nlogn) 평균도 O(nlogn) 으로 안정적이고 빠른 성능을 보여줍니다.

[Kiyoung-Kim-57]

Swift의 기본 정렬 알고리즘은 과거엔 IntroSort 알고리즘을 사용했다. 이는 상황에 따라 삽입, 힙, 퀵 정렬을 사용하는 하이브리드 정렬 알고리즘이다. 현재는 TimSort라는 삽입정렬과 병합정렬의 하이브리드 정렬방식을 사용하고 있다.
TimSort는 먼저 배열을 작은 단위의 서브시퀀스로 나누고 각 서브시퀀스들 중 정렬이 안된 시퀀스를 삽입정렬로 정렬한다. 그리고 정렬된 서브시퀀스들은 병합정렬로 정렬하여 마무리한다. 해당 정렬은 최악의 상황에서 O(nlogn)의 성능을 보여준다.
특히 이미 정렬이 이루어진 서브시퀀스들을 활용하기 때문에 어느 정도 정렬이 이루어진 배열에서 성능이 좋다.

[hsw1920]

Swift에서 제공하는 표준 라이브러리의 sort()는 Timsort로 구현되어있습니다.
TimSort는 MergeSort와 InsertionSort를 하이브리드한 정렬 알고리즘입니다.

Merge, Insertion 정렬이 모두 stable 하기 때문에 TimSort또한 stable을 유지하며, 이에따라 중복값이 존재할때 정렬 전후 중복 값의 순서를 유지합니다.
TimSort는 run이라는 단위로 배열을 분할하고 분할한 단위에 대해 InsertionSort를 수행하고, 이를 Merge하는 방식으로 두 정렬방식을 혼합하여 정렬을 수행합니다.

TimSort는 대부분 사용되는 배열이 완전 무작위가 아닌 점에서 정렬을 최적화한 좋은 예시로 최선의 경우 O(n), 최악의 경우에도 O(nlogn)의 시간복잡도로 동작합니다.

[0Hooni]

🙋🏻 답변

Swift 라이브러리에서 기본적으로 제공되는 정렬알고리즘으로는 Intro 정렬과 Tim 정렬을 사용합니다.

Intro 정렬의 경우 삽입정렬, 퀵정렬, 힙정렬을 섞어 하이브리드 방식으로 정렬 알고리즘을 수행합니다. 학습한바로는 전체, 혹은 부분의 크기가 16 이하인 경우 삽입정렬을 사용하고, 그 이상인 경우는 퀵정렬을 사용합니다. 그 과정에서 퀵정렬의 깊이가 특정 임계치를 넘어가면 힙 정렬로 스왑하여 정렬을 수행합니다.

그리고 2018년 이후 swift에서 정렬 방식을 수정했는데, 그 방식이 Tim 정렬입니다. 해당 방식은 삽입 정렬과 병합 정렬을 혼용하는 하이브리드 정렬 알고리즘입니다. Tim 정렬에서는 Run이라는 단위로 배열을 분할하고 이 분할된 단위에 삽입 정렬을 수행한 뒤 이를 합쳐서 정렬을 수행합니다. 이 때 Run의 크기가 분할 전에 결정된 최소 Run의 크기보다 작을 경우 최소 Run이 될 수 있도록 배열을 확장합니다. 이러한 이유는 병합 정렬에서 최소한 적을 횟수로 병합하기 위함입니다.

Swift에서는 최종적으로 이러한 방식의 Tim 정렬을 사용하여 기본적인 정렬 알고리즘으로 동작하고 있습니다.

🏷️ 키워드

IntroSort, 동작방식, 부분크기, 삽입정렬, 퀵정렬, 정렬전환, 힙정렬, TimSort, Run, minRun, 삽입정렬, 병합정렬