Swift에는 sort라는 함수가 있다.
정렬에 대한 모의면접을 봤는데 iOS에는 어떤 sort가 쓰일까요?난 대답하지 못했다.
sort에 대해서 사용만 해봤지 sort 알고리즘에 대해서는 생각하지 못했다.
modified timsort
Swift는 2018년에 modified Timsort로 교체했다고 Issue가 남아있었다.!
수정된 Timsort.... 우선 Timsort가 무엇인지에 대해서 알아보자.
Timsort는 하이브리드 알고리즘이다.
전기랑 기름으로 가는 차를 하이브리드차 라고 하듯이 2개 이상의 알고리즘을 섞은 것을 하이브리드 알고리즘이라고 한다.
그럼 이름에 담긴 뜻 Tim은? 최초 고안해낸 Tim Peter의 성을 땄다.
요약하면 다음과 같다,
1. 일정한 규칙에 의해서 배열의 크기를 나눈다. <RUN>
2. 나눠진 배열을 Binary Insertion Sort 알고리즘을 사용하여 정렬한다.
3. 나눠진 배열을 병합배열을 통해서 정렬 알고리즘을 완성시킨다.
이 때 배열이 너무 작으면 나뉘지 않고 이진 삽입 정렬(Binary Insertion Sort) 알고리즘이 작동되는 것으로 보인다.
* 이진 삽입 정렬 (Binary Insertion Sort)
삽입 정렬에서 새로운 숫자를 삽입 해야 할 때 이미 정렬된 배열을 모두 훑어야 했다.
이 때 이진 삽입 정렬은 모두 훑는 것이 아니라 이진 탐색을 통해 새로운 숫자 넣는 곳을 찾는 것이다.
이를 통해서 O( n log n )이 나온다. 하지만 최악의 경우 O (n ^2 ) 이 나온다. ( 오름차순 정렬을 원할 때 배열이 내림차순으로 정렬된 경우)
아래 유튜브가 아주 잘 설명해주고 있다.
움... 더 자세히 공부하고 싶은데 나눠진 배열을 나누는 방식에 대해서는 잘 모르겠다...
더 공부해야 겠다.
'Swift > Apple Framework' 카테고리의 다른 글
| [iOS / SwiftUI] Combine - CurrentValueSubject, PassthroughSubject (0) | 2023.05.02 |
|---|---|
| [SwiftUI] StateObject와 ObservedObject 차이점 (0) | 2023.04.22 |
| [iOS / SwiftUI] Combine - 맛보기 (2) | 2023.04.21 |
| [iOS / Swift] Cache (0) | 2023.04.19 |
| [SwiftUI] LazyVGrid / LazyHGrid (0) | 2023.04.18 |
