1. 첫째 줄에 수의 개수 N(1<=N<=1,000,000)이 주어진다. 배열의 크기가 백만이 넘어야하는데, 십만을 하셨네요!
2751번 - 수 정렬하기 2
1. 첫째 줄에 수의 개수 N(1<=N<=1,000,000)이 주어진다. 배열의 크기가 백만이 넘어야하는데, 십만을 하셨네요!
stl sort는 퀵정렬로 구현되어있는걸로 알고 있는데요...
stl stable_sort는 병합정렬로 구현되어있어 항상 nlogn이 걸립니다.
stl의 정렬 알고리즘은 정확히 말하자면 퀵 소트가 아닙니다. 엄밀히 말하자면 intro sort라는 알고리즘을 쓴다고 말할 수 있습니다.
앞서 말씀해주신 것처럼 최악의 경우에도 O(nlogn)을 유지해주기 위한 변형이 가해진 알고리즘이고, 그래서 정확히는 퀵소트라고 말할 수 없는 알고리즘이죠(엄밀히 따지자면 동작이 다른 알고리즘이므로). 비교 기반의 정렬 알고리즘은 이보다 더 빠를 수 없고, stl sort 구현이 속도가 느린 구현이 아니기 때문에 일반적으로 정렬이 필요한 상황에서는 그냥 쓰시면 됩니다. 이 문제의 경우 sort가 느려서 안 쓴 사람이 많다기 보다는 정렬 알고리즘 구현을 한 번 연습해보고자 하는 용도로 직접 구현해 보신 분들이 많은 거 일 거에요.
introsort에 대한 자세한 내용은 위키 피디아 참조해보시면 될 것 같습니다.
댓글을 작성하려면 로그인해야 합니다.
justking 6년 전
stl 의 sort 안쓰고거의 quick sort, merge sort로 풀었던데 이걸로는 원래 못푸는건가요?