swift 내의 sort 가 어떻게 구현되어있나요?

[co3oing]

swift5 이전에는 Quicksort와 Heapsort, Insertionsort로 구현된 introsort로 구현이 되어있었습니다. 20개 미만의 작은 배열은 Insertionsort로, 배열이 작지 않은 경우에는 Quicksort로 재귀가 깊어지면 Heapsort로 전환되는 방식으로 동작하여 O(n log n)을 보장합니다. 하지만 메모리 사용 측면에서 일반적인 정렬 알고리즘보다 성능이 약간 떨어지고, swift는 꼬리 재귀 호출이 최적화될 것이라고 보장하지 않고, 불안정한 Quicksort와 Heapsort로 구현된 알고리즘이기 때문에 swift5 부터 Timsort로 변경되었습니다.

Timsort는 Tim Peters가 파이썬에서 사용하기 위해 구현한 정렬 알고리즘으로 병합 정렬과 삽입 정렬로 구현되어있습니다. Timsort는 배열을 더 작은 섹션으로 나누고 삽입 정렬로 더 작은 섹션을 정렬한 후 병합 정렬로 섹션을 병합하는 방식으로 작동합니다. 삽입 정렬, 병합 정렬 모두 안정적이기 때문에 Timsort도 안정적이며 최선의 경우 O(n), 최악의 경우 O(n log n)의 복잡도를 가져 훨씬 빠릅니다.

[sustainable-git]

Swift의 sort()는 Insertion Sort와 Merge Sort가 합쳐진 형태인 Tim Sort로 구현되어 있습니다. Programmer가 실제로 마주하게 되는 배열이 완전 무작위가 아닌, 어느정도 정렬된 배열인 경우가 많기에 정렬된 상태에서 가장 효과적인 Insertion Sort를 이용해 최적화했습니다. Tim Sort는 Run이라는 단위로 분할 후, Insetion Sort를 수행하고 merge하는 방식입니다.

[tmfrlrkvlek]

Swift의 sort() 함수는 Timsort 알고리즘을 사용하여 구현되었습니다.

Timsort는 최고 O(n) ~ 최악 O(nlogn) 의 시간 복잡도, n의 공간 복잡도를 가지고 stable 하며, 다양한 데이터에 적합한 알고리즘입니다.

Timsort는 Insertion sort와 Merge sort 알고리즘을 섞은 것으로 그 과정은 다음과 같습니다.

1. run으로 분할하여 Insertion 정렬한다. (32 ≤ run의 크기 ≤ 64)
2. run들을 stack 형식으로 쌓는데 다음 조건을 만족해야 한다.
   1. 위에 쌓이는 run(A)의 length가 바로 아래에 있는 run(B)의 length보다 작아야 한다. A < B
   2. 위의 연속된 두 run(A, B)의 length의 합이 바로 아래 run(C)의 length보다 작아야 한다. A + B < C 둘 중 하나라도 만족하지 않으면 A와 B 모두를 pop하여 A와 B를 merge 한다. A + B를 다시 stack에 집어넣는다. stack에 넣을때는 배열을 모두 넣는 것이 아니라, 배열의 시작 인덱스와 마지막 인덱스만 집어 넣는다.
3. stack에 쌓인 run들을 최적화 트릭을 사용하여 병합한다.

이렇게 Timsort는 할 수 있는 모든 최적화 트릭을 사용하여 설계한 알고리즘입니다.

참고 영상 : https://www.youtube.com/watch?v=2pjUsuHTqHc

[inuinseoul]

• 기존에는 quicksort와 heapsort를 섞은 introsort라는 알고리즘을 사용했습니다. 2018년에 merge sort 및 insertion sort에서 파생된 timsort로 변경되었습니다.
• 세부내용 참고 : http://www.secmem.org/blog/2019/04/10/special-sorts/

introsort

• 전체적인 흐름은 quick sort와 동일하지만, maxdepth라는 변수를 두어서 일정 횟수 이상 재귀로 들어가면 더 이상 quick sort를 하지 않고 항상 O(NlogN)의 시간 복잡도를 보장하는 heap sort를 수행합니다.
• cf. quick sort : pivot을 정하고 그 pivot보다 크기가 작은 것은 왼쪽, 큰 것은 오른쪽으로 이동하는 것을 반복하여 정렬하는 방식 (시간복잡도 O(N^2), not a stable sort)
• cf. heap sort : heap 자료구조를 활용한 정렬 방식 (시간복잡도 O(NlogN), not a stable sort)

timsort

• insertion sort + merge sort + a의 정렬 알고리즘입니다. run이라는 단위로 배열을 분할하고 각 분할 단위에 대해 Insertion Sort를 수행한 다음 이를 합치는 방식으로 정렬을 수행합니다.
• cf. insertion sort : 배열의 일부를 정렬된 상태로 유지하면서 다음 원소의 위치를 정렬된 부분에서 찾아 삽입하는 방식 (시간 복잡도 O(N^2), stable sort)
• cf. merge sort : 주어진 배열을 작게 분할한다음 다시 합치면서 정렬하는 방식 (시간 복잡도 O(NlogN), stable sort)

[duyeonnn]

swift의 sort 메서드는 time sort로 구현되어있다. time sort는 merge sort와 insertion sort가 섞여있는 방식으로 O(nlogn)의 시간복잡도를 가진다. insertion sort도 stable하고 merge sort도 stable하므로 tim sort또한 stable 하다. time sort는 다음과 같은 과정을 거친다.

1. minRun 상수 구하기: 가장 먼저, 배열을 분할할 크기 단위를 정하는 과정을 수행한다. 이를 minRun이라고 하며, 이 값은 배열의 크기 값에 따라 유동적으로 정해진다. Swift에서는 크기 64 이하의 배열에서는 배열의 크기로, 그 이상에 대해서는 비트의 배열에 따라서 32~64 사이의 값을 가지게 된다.
2. run 만들기: 이후 non-descending(뒷 원소가 앞 원소보다 크거나 같다) 혹은 strictly descending(뒷 원소가 앞 원소보다 작다) 조건을 만족하는 크기로 배열을 분할한다. 이후 strictly descending한 경우, 배열을 뒤집는 과정을 거친다. 이 때 분할한 배열의 크기가 minRun보다 작은 경우에는 minRun 크기가 되도록 배열을 확장한 뒤, Insertion Sort로 정렬한다. 이는 최대한 적은 횟수로 머지를 수행하기 위해서는 조각의 크기가 균일해야 하기 때문이다. 이렇게 만들어진 부분 배열을 Run이라고 하며, 이후 이를 스택에 넣는다. 실제 구현에서는 배열을 직접 자르는 게 아니라 범위로 나타남.
3. Merge 혹은 다음 Run 구하기: 스택에 Run이 쌓였을 때, 이를 바로 Merge할 지 말지를 결정해야 한다. swift의 TimSort에서는 다음과 같은 전략을 취한다.

1. 스택의 위에서부터 4개의 Run을 차례대로 X,Y,Z,W라고 하면, 다음 불변식을 만족해야 합니다.
   2. 스택 크기가 4이상 일 경우, |W| > |Z| + |Y|
2. 스택 크기가 3일 경우, |Z| > |X| + |Y|
3. **스택 크기가 2인 경우, |Y| > |X|**
4. ****만약 조건을 만족하지 않는다면 Y를 X와 Z 중 작은 쪽과 합친다
5. 불변식을 만족하거나 스택 크기가 1이 되면 Merge를 종료하고 다음 Run을 구한다.*

4. 배열의 끝에 다다를 경우, 스택에 쌓여있던 모든 Run을 위에서부터 합쳐서 하나로 만든다.

[dailynj]

swift 내에서는 insertionSort 와 MergeSort 를 합친 timeSort 라는 알고리즘은 사용한다고 합니다. timeSort 는 run 이라는 단위로 분할을 하고 분할된 단위는 insertionSort 하고 다시 merge 하는 방식으로 정렬한다고 알고있습니다. 이는 최선의 경우 O(n), 최악의 경우 O(n log n )의 시간 복잡도를 가집니다.