안정 불안정 정렬?
정렬에는 많은 방법이 있다. 버블 정렬, 삽입 정렬, 퀵 정렬 등등,, 하지만 이러한 정렬 알고리즘의 시간 복잡도가 모두 다르듯이, 정렬의 결과 또한 다를 수가 있다.
안정 정렬
안정 정렬은 쉽게 생각해서 기본 값을 유지하는 정렬이다. 정렬을 해야하는데 기본 값을 유지한다는 것이 이해가 되지 않을 수 있다.
그림을 살펴보자
위의 줄을 sort 오름차순으로 정렬한다고 할 때, 8은 중복이 되어 있다. 하지만 오름차순 정렬 결과를 보면 파란색8 -> 빨간색8 의 규칙은 유지하고 있다. 이렇듯 정렬을 한 후에도 동일 값에 대한 순서를 유지하는 것이 안정 정렬이다.
불안정 정렬
위의 예시와 설명을 이해한다면 불안정 정렬을 쉽게 유추할 수 있을 것이다. 불안정 정렬은 안정 정렬과는 다르게 기본 순서를 보장하지 않는다는 것이다.
정렬 후에 파란색8 -> 빨간색8 이라는 순서를 보장하지 않는다.
안정 정렬에는 아래의 정렬 알고리즘이 있다.
삽입정렬병합정렬버블정렬
불안정 정렬에는 다음과 같은 정렬이 있다.
퀵 정렬선택정렬계수정렬
이러한 정렬 알고리즘을 사용할 때 안정 정렬인지 불안정 정렬인지 알고 쓰는 것은 유용해 보인다.
동구팔