[Swift] Swift의 sort() 메서드에 대하여

💬 시작하며

정렬 알고리즘을 공부하면서 sort()에 대해서 궁금해졌다. 그리고 코딩테스트에서 정렬알고리즘도 어떻게 사용되는지 궁금해졌다. 코테에서는 대부분 정렬을 원할 때 Sort() 메서드를 사용해서 정렬시키기 때문이다. 단순히 알고 넘어가야만 하는 개념인건지, 아니면 구현까지 모두 완벽하게 할 줄 알아야하는건지?
 

⚫️ Swift의 sort() 내부 알고리즘 변화

▪️ 2018년 이전

Swift는 2018년 sort의 내부 알고리즘이 교체가 됐다. 원래는, introsort를 사용했었다.

introSort

introsort란 평균적으로 빠른 성능을 내면서 최악의 상황에서도 점진적으로 최적화된 성능을 제공하는 하이브리드 정렬 알고리즘이다. C++ STL에서도 기본적으로 제공되는 정렬 함수이다.
intro 정렬은 힙정렬, 퀵정렬, 삽입정렬로 이루어져있다. 기본적으로 퀵정렬을 사용하는데 퀵정렬은 최악의 경우에 느려지게 되고, 이 단점을 보완한 알고리즘이 바로 introSort라고 할 수 있겠다.
최악의 경우 단점을 보완해서 사용하는 하이브리드 정렬 알고리즘이기 때문에 최악의 경우에도 시간복잡도 O(nlogn)을 보장한다.

introsort 동작방식

1. 리스트의 크기가 16이하인 경우라면, 삽입정렬을 채택한다.
2. 전체 리스트에 대해서 퀵정렬을 수행한다.
3. (퀵 정렬은 최악의 경우 O(n^2) → 분할 횟수가 많아지면 성능이 저하, 분할 횟수가 특정 임계치에 도달하면 sort 방식을 스위칭 하는 방식을 채택 → 그래서 최악의 경우에도 시간복잡도가 O(nlogn)임)
4. 수행 도중 재귀 호출의 깊이가 2logn을 넘어가면 4번항목(힙정렬로 스위칭)으로 넘어간다.
5. 쪼개진 부분 리스트의 크기가 16이하라면 그대로 놔둔다.
6. 16보다 크면, 해당 부분 리스트에 대해 힙정렬을 수행한다.
7. 3, 4번 항목이 모두 완료된 후, 대부분 정렬이 된 전체 리스트에 대해서 삽입정렬을 수행한다.

뭐 대충,, 이렇게 여러가지 정렬 방식의 장점만 골라서 사용한다고 알고 있어보자. (아직 잘 어케 동작한다는지 이해는 안되지만,,)
 

▪️ 2018년 10월 이후

Swift의 sort 알고리즘이 Timsort로 교체됐다.

https://github.com/apple/swift/pull/19717

[stdlib] Switch to a stable sort algorithm by natecook1000 · Pull Request #19717 · apple/swift

 
해석해보자면,

This switches the standard library's sort algorithm from an in-place introsort to use a modified timsort, a stable, adaptive sort that merges runs using a temporary buffer.

표준 라이브러리의 정렬 알고리즘을 in-place introsort에서 임시 buffer를 사용하여 실행을 병합하는 안정적이고 적응적인(?) 정렬인 modified timsort를 사용하도록 전환한다.
(in-place sorting이란, 제자리 정렬을 의미하는데, 임시배열 필요 없이 배열 내부에서 정렬을 하는 것을 제자리정렬이라고 하는가보다. 임시배열이 필요하다면, inplace 정렬이 아님! (참고 - https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html)

In addition to maintaining the relative order of equal/non-comparable elements, this algorithm outperforms the introsort on data with any intrinsic structure, such as runs of ascending or descending elements or a significant number of equality collisions.

이 알고리즘은 equal / non-comparable 요소들의 순서를 유지할 뿐만 아니라 (stable, 안정정렬이라는 뜻인거같음) 오름차순, 내림차순 요소 실행 / equality collisions와 같은 것들에서 introsort를 훨씬 능가한다.
뭐 어쨌든, introsort보다는 더 좋은 성능의 timsort를 이용하게끔 바꿨다는 말이다. 음… 지금 나의 추측으로는 퀵정렬, 힙정렬을 사용하는 introsort는 불안정정렬이기 때문에 안정정렬을 사용하도록 바꿨다! 그래서 뭐 이런이런 충돌 이런것에서 능가한다. 이런 느낌쓰 인것 같았다.
(불안정 정렬 / 안정정렬 참고자료 https://velog.io/@good159897/안정-정렬-VS-불안정-정렬-파이썬-알고리즘-인터뷰)

 

⚫️ timsort

▪️ timsort가 뭘까

timsort는 삽입정렬과 병합정렬을 사용하는 하이브리드 정렬 알고리즘이다. 이 두가지에 대해서 먼저 알아보자.

Insertion sort (삽입정렬)

 
삽입정렬은 배열의 일부를 정렬된 상태로 유지하면서, 다음 원소가 있어야할 위치를 살펴보면서 정렬을 수행하는 알고리즘이다. 아래 내가 잘 정리해두었으니, 살펴보자.
https://desert-opossum-095.notion.site/b962ec3c29fb45aab515af5765e7c784

삽입정렬

Merge sort (병합정렬)

merge sort는 주어진 배열을 작은 크기로 쪼개서 정렬한 뒤에, 이를 순차적으로 합치는 정렬 방식이다. 분할하는 방법에는 여러가지 방법이 있지만, 주로 절반씩 쪼개서 합치는 분할 정복 기법을 사용한다.

https://jcsoohwancho.github.io/2019-11-20-Swift%EC%9D%98-%EA%B8%B0%EB%B3%B8-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Timsort/

병합정렬은 분할을 할 때마다 문제 크기가 절반으로 줄어든다. 대신, 문제의 개수는 2배로 늘어나게 된다. (병합해야하는 배열이 2배씩 늘어난다는 뜻) 이 부분 문제들을 O(1) 로 정렬할 수 있을 때 까지 (원소가 1개일때까지) 수행되고, 이 문제들은 O(N)의 시간복잡도를 가지는 알고리즘으로 합쳐진다. 이 합쳐지는 과정은 문제의 개수에 대해서 비례해서 이루어지기 때문에 전체 시간복잡도는 O(nlogn)이 된다.
병합정렬은 데이터의 분포의 영향을 덜 받는 stable한 정렬 방법이다. 즉, 입력 데이터가 무엇이든 간에, 정렬되는 시간은 O(nlogn)으로 동일하다.
시간복잡도 증명은 이 글을 참고하자 https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

▪️ timsort

위에서 설명한 두 가지의 알고리즘을 사용하는 하이브리드 정렬 알고리즘이다.
Run 이라는 단위로 배열을 분할하고, 이 분할된 단위에 대해서 삽입정렬으 수행한 뒤, 이를 합쳐서 정렬을 수행한다. (병합정렬)

동작 방식

1. minRun 상수 구하기 - 배열을 분할할 크기 단위를 정하는 과정
2. run 만들기 - 조건을 만족하는 크기로 배열을 분할하는 과정
   • 분할한 배열의 크기가 minRun보다 작으면, minRun이 되도록 배열을 확장한뒤, 삽입정렬로 정렬
   • 확장이유? 최대한 적은 횟수로 merge하기 위해서는 크기가 동일해야하기 때문!
   • 이후 이 run들을 stack에 넣는다.
3. merge 하거나, 다음 run 구하기 - stack에 쌓인 run들을 머지할지말지 결정해야한다.
   • 스택의 위에서부터 4개의 run을 x, y, z, w 라고 하면
     • 스택의 크기가 4 이상인 경우 |w| > |Z| + |Y|
     • 스택의 크기가 3일 경우 |Z| > |X| + |Y|
     • 스택의 크기가 2일 경우 |Y| > |X|
   • 만약 조건을 만족하지 않으면, Y를 X와 Z중 작은쪽과 합침
   • 위 조건을 만족하거나, stack의 길이가 1이 되면 merge를 종료하고 다음 run을 구함

시간복잡도

timsort는 배열이 무작위가 아니라는 점에서 정렬을 최적화한 좋은 예로, 최선 O(N), 최악 O(nlogn)을 보장한다.
(참고 - https://jcsoohwancho.github.io/2019-11-20-Swift의-기본-정렬-알고리즘-Timsort/)

 

⚫️ swift sort 코드는 여기서 볼 수 있음

지금 해석해보진 않을거고 시간되면 살펴보기..
https://github.com/apple/swift/blob/main/validation-test/stdlib/Sort.swift.gyb

GitHub - apple/swift: The Swift Programming Language

 
 

🔖 위에서 작성하지 않은 추가의 참고자료 

https://brunch.co.kr/@joonwonlee/8
https://justicehui.github.io/medium-algorithm/2019/03/24/IntroSort/