stable sort와 unstable sort의 차이점

Definition

어떤 리스트를 정렬 할 때, 결과 값은 똑같지만 내부 정렬과정이 다름으로 인해서 생겨나는 차이점을 구분하기 위해서 stable한 정렬법과 unstable한 정렬법으로 나뉘어 집니다.

stable한 정렬은 리스트의 원래 위치를 보존하며 리스트를 정렬합니다.
unstable한 정렬은 리스트의 원래 위치를 보존하지 않으며 리스트를 정렬합니다.

예제

[A, C, A, B, C, D]
위와 같은 정렬이 있을때, 사전식 오더로 정렬을 하면, [A,A,B,C,C,D]라고 정렬이 됩니다.
하지만 이는 첫번째 순서에 나온 A와 두번째 나온 A를 구분지어서 생각하면 구분이 가능합니다.

[A(1), C(1), A(2), B, C(2), D]

sable sorted
[A(1), A(2), B, C(1), C(2), D]
unstable sorted
[A(2), A(1), B, C(1), C(2), D]

Stable Sorting의 예시

Bubble Sort
Insertion Sort
Merge Sort
Counting Sort
Bucket Sort
Radix Sort

Unstable Sorting의 예시

Selection sort
Heap Sort
Shell Sort
Quick Sort