[정렬] sort

버블정렬, 선택정렬, 삽입정렬, 쉘정렬,

병합정렬, 퀵정렬, 힙정렬,

계수정렬, 기수정렬까지...

많은 정렬들을 직접 구현해봤지만, 결국 실전에서는 이것들을 일일이 구현할 순 없다.

물론, 다 외워서 할 수 있으면 정말 좋긴 할 것이다.

실전에서 만약 정렬이 필요하다면,

#include <algorithm>
sort(v.begin(), v.end());
stable_sort(v.begin(), v.end());

STL함수를 써야할 것이다.

sort

여기 있는 sort함수는 introsort라는 하이브리드 기법을 썼다고 한다. 불안정한 quick sort가 아니라서 다행이다.
시간복잡도 O(NlogN)을 보장한다.

stable_sort

또한 중복되는 key에서 각 key가 가진 다른 값도 정렬하고 싶을 때는 stable_sort를 이용하면 된다.

이는 merge sort를 이용한다. 여분의 메모리 공간이 필요한 정렬이다.
메모리공간이 있다면, 시간복잡도 O(NlogN)을 보장한다.