5장 정렬 - (5) Stable Sorting

1. Stable Sorting

-같은 것이 있는 경우에 정렬하기 전의 순서가 유지되는 정렬 알고리즘

-예를 들어, 다음을 숫자가 증가하는 순서로 정렬했을 때

    5○, 4○, 3○, 3●, 2○, 1○ 

=>1○, 2○, 3○, 3●, 4○, 5○ 

또는

=>1○, 2○, 3●, 3○, 4○, 5○

위와 같이 3에 대해서 두 가지의 결과가 나올 수 있다.

이 때, 첫번째 결과처럼 정렬하기 전의 순서가 유지되는 정렬 알고리즘이 stable 한 정렬이다.

2. 시간복잡도가 N^2인 stable sorting

-버블 정렬

3. 시간복잡도가 NlgN 인 stable sorting 

-병합 정렬(Merge Sort)

-STL에는 stable_sort 알고리즘 사용

4. 문제

-10814번(나이순 정렬)

-10825번(국영수)

-10989번(수 정렬하기 3)