TimSort의 단점이 뭘까요?

Question

코테 도중 시간복잡도를 측정하고자 Tim Sort에 대해 공부해보았고 이에 대해 정리하고 있는데요 내가 이걸 언제 어떻게 왜 쓰는지 정리하고 있었습니다. 그런데 단점에 대해서 쓸만한 내용을 찾지도 못 하고, 생각도 나질 않네요시간도 다른 정렬에 비해 월등히 우수하고, 메모리도 O(n)으로 준수한데요. Run에 대해 내부적으로 Insertion Sort가 진행된다는 것 외에는 단점(?)을 찾지 못 하겠습니다.혹시 TimSort의 단점은 뭐라고 생각하시나요?

Clickin · Answer

일반적으로 사용하는 소트 알고리즘은 메모리 복잡성, 바이너리 코드 크기 같은 요소는 상대적으로 중요도가 낮습니다.하지만 임베디드 시스템에서는 제한된 가용자원때문에 바이너리 크기가 작게 나오는 쉘 소트가 많이 사용된다는 글을 읽은 적이 있습니다.찾아보니 https://embeddedgurus.com/stack-overflow/2009/03/sorting-in-embedded-systems/ 이거네요

머리가아파요 · Answer

일반적으로 큰 단점 없습니다. 사용 용도가 명확하거나 인풋을 대강 알고 있는 상황에서는 그에 맞는걸 쓸뿐...(리눅스 커널에서 메모리 때문에 힙소트 사용 등)

TimSort의 단점이 뭘까요?

2개의 답변

#sort 목록