Swift ) Swift Sorting Algorithm

안녕하세요 :) Zedd입니다. 

늦었지만.....메리크리스마스~~~~~~~~

백준의 수 정렬하기 3...

이 문제로 말할 것 같으면...

Swift로 맞은 사람이 단 한명도 없는 문제...

암튼 위 문제를 Swift로 대충 풀어보면 

Swift에서 제공해주는 sort()라는 메소드를 쓸 생각을 가장 먼저 하겠죠? 

그러며는~~시간초과가 난다~~라는 것.

위 문제는 C++로 풀어도 그냥 C++ STL에 있는 sort를 써도 시간초과가 납니다..

그래서 Counting sort?라는 방법을 이용해서 풀어야 한다고 하는데요.

C++로 풀면 

맞았습니다..를 볼 수 있습니다.

import Foundation

let num: Int = Int(readLine()!)!

var array: [Int] = Array(repeating: 0, count: 10001)

for _ in 0..<num {

    let n = Int(readLine()!)!

    array[n] += 1

}

for i in 1...10000 where array[i] > 0 {

    for _ in 0..<array[i] {

        print(i)

    }

}

악 강제 언래핑이 많은 이유는 음..

저는 강제언래핑에 대ㅐ해서 뭐어??!? 느낌표?!?!? < 인 사람이 아니라서..

값이 있는 걸 확신 할 수 있을 때 쓰라고 만들어진 기능 아니겠어요?

애플도 그렇게 말하기도 했고 ㅋ_ㅋ

그리고 PS다 보니..100%확신 할 수 있는 상황

자 계속하면

C++로 맞았습니다 뜬 코드를 그대로 Swift로 컨버팅한 코드입니다. 

위 코드를 제출하면 맞을 것 같지만 또 시간초과가 뜹니다.

이건 언어의 한계구요. 시간초과가 떴다고 당황하시면 안됩니다.

이럴때는 그냥 포기해야합니다. 뭐를? Swift로 푸는 걸 ㅇㅇ

애초에 C++이랑 Swift를 시간으로 비교를 한다는거 자체가 저는 개오바쎄바라고 생각하는 주의라서...

백준에 언어별로 시간제한을 주는게 있는데..

그니까 Swift로 풀었을 때 더 많은 시간을 주면 아마 풀수있을지 모르지만 

코틀린은 있는데...Swift가 없다....?

그럴 수 있죠!! 안드로이드 짱!!!

암튼 안풀리는 문제는 끝까지 안풀립니다. 이러면 풀리지않을까? < 안풀립니다.

제 경험상 그렇구요.......그렇던데..저는........

암튼 Swift로 PS하시는 분들에게 그냥..언어의 한계를..알려드리고 싶어서 구구절절 이야기 했구요.

오늘의 주제는 Swift가 사용하는 sort알고리즘입니다. 

Swift가 사용하는 sort알고리즘

---

음..Swift가 사용하는 sort알고리즘을 검색해보시면 

introsort를 쓴다고 알려져있는데요,

위키를 간단히 요약해보면

하이브리드 정렬 알고리즘이라고 하는데요,  

recursion depth가 정렬할 요소의 수에 기초한 수준을 넘어설 때, 

quicksort로 시작하여 heapsort로 전환된다고 해요.

그냥 간단하게..quicksort와 heapsort의 좋은 부분을 합쳤다고 생각하면 될 것 같아요.

C++ STL의 sort알고리즘도 이 introsort라고 하는데..! 

지금도 그런지는 확실하게 모르겠어요. 암튼 

https://en.wikipedia.org/wiki/Sort_(C%2B%2B)

에 가면 그렇다고 함 ㅇㅇ

시간복잡도는 최악의 경우 O(NlogN)이라고 합니다. 

암튼 Swift가 introsort를 쓰는...............줄 ㅇ알았지만..

2018년. 올해죠?

2018년 10월에 

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

Swift의 sort알고리즘이 교체가 됩니다.

첫줄에서,

"This switches the standard library's sort algorithm 

from an in-place introsort to use a modified timsort"

in-place introsort에서 modified timsort로 전환됐다고 하죠?

이 알고리즘(modified timsort)는 동일하거나 비교불가능한 요소의 상대적 순서를 유지하는 것 이외에도,

ascending(오름차순) 또는 descending(내림차순) 요소 실행 / 상당한 수의 equality collisions(이걸 뭐라 번역해야할지 모르겠음. 등가 충돌?)

과 같은 것에서부터 introsort를 능가(outperforms)한다고 합니다.

아무튼...그렇다고 합니다...

Swift개발자가..그렇다고 하니..뭐 그렇지 않겠어요?!?!?!

그렇다면 이 timsort가 머냐..

또 modified timsort가 머냐...........

암튼 timsort를 일단 봅시다.

"Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data."

timsort는 다양한 종류의 실제 데이터에서 잘 수행되도록 설계된, 

merge sort 및 insertion sort에서 파생 된 안정적인 하이브리드 정렬 알고리즘입니다. 

이 알고리즘은 이미 정렬된 데이터의 subsequences를 찾아서, 

그 지식?(knowledge)을 사용하여 나머지를 보다 효율적으로 정렬한다고 해요. 

오 이 timsort가 파이썬에서의 sort 알고리즘 인가봐요. 

그리고 안드로이드, 구글 크롬에서도 기본타입의 배열을 정렬하는데 이 timsort를 사용한다고 합니다. 

최악의 경우 O(NlogN)의 시간복잡도를 가집니다. 

최적은 O(N)이라고 해요. 

modified timsort는 잘 모르겠음..왜 안나오지? 

뭐가 수정된거지? 

아..그 

첫번째 문단에 마지막줄 보면, 

timsort의 galloping strategy를 채택하는 대신, straight merges를 수행한다고 하는데..

이거때문에 modified timsort인가..?

암튼..이건 패스

Swift의 sort가 어떻게 구현되어있는지 궁금하신 분들은

Swift의 Sort소스코드를 참고하세요. 

ㅎㅎ

새로운 걸 알아서 기분이 좋네요. XD

도움이 되었길 바래요!!