1. 정렬의 Stability(안정성?)
같은 Key 를 가진 원소들이 소팅 전후로 순서가 바뀌나 안바뀌나를 의미한다.
2. 정렬의 안정성이 중요한 이유
키가 여러 개인 이유 stability이 중요해진다.
how much wood would woodchuck chuck if woodchuck could chuck wood 를
알파벳 순으로 그리고 빈도 수 순으로(내림차순) unstable 하게 정렬한다고 생각하자.
1) 단어 빈도수를 계산한 테이블은 다음과 같고
how 1
much 1
wood 2
would 1
woodchuck 2
chuck 2
if 1
could 1
2) 알파벳 순으로 먼저 정렬하면
(chuck, 2)
(could, 1)
(how, 1)
(if, 1)
(much, 1)
(wood, 2)
(woodchuck, 2)
(would, 1)
3) 그 후 빈도수로 unstable하게 정렬하면 (대표적인 unstable sort인 quick sort를 이용하면)
(wood, 2)
(chuck, 2)
(woodchuck, 2)
(could, 1)
(how, 1)
(if, 1)
(would, 1)
(much, 1)
기존에 알파벳으로 순서 조정한게 깨진다.
즉 키가 여러 개인 경우는 stable하게 정렬해야한다.
4. Stable and Unstable 정렬 알고리즘
stable : merge sort, insertion sort, count sort, bubble sort
unstable : quick sort, heapsort, selection sort
바로 옆에 원소랑 비교연산을 하는 정렬들은 stable 하고
그렇지 않은 경우는 unstable 하다는 것을 알 수 있다.
stable sort는 대체적으로 느리기 떄문에 정렬할 대상을 생각하고 정렬 알고리즘을 선택해야한다.
(merge sort는 시간복잡도가 O(NlogN)이지만 같은 시간복잡도인 quicksort보다 상수가 크다고 알려져있다.)