Tech.log/알고리즘
[Stable Sort(안정 정렬) vs Unstable Sort(불안정 정렬)]
SpaciousKitchen
2021. 5. 29. 14:25
2021.05.10 - [Tech.log/알고리즘] - [정렬 방법]
정렬을 잘 모른다면, 해당 글을 먼저 참고하자.
Stable Sort(안정 정렬)
동일한 정렬 기준을 가진 것은 정렬을 한 후에 위치가 동일하다.
ex)5 9 3’ 7 2 3 => 2 3’ 3 5 7 9
Bubble Sort(버블 정렬)Insertion Sort(삽입 정렬)Merge Sort(합병 정렬)
Unstable Sort(불안정 정렬)
동일한 정렬 기준을 가진 것은 정렬을 한 후에 위치가 동일하지 않을 수 있다.
ex)5 9 3’ 7 2 3 => 2 3 3’ 5 7 9
Selection Sort(선택 정렬)Quick Sort(퀵 정렬)Heap Sort(힙 정렬)
UnStable한 이유
Selection Sort(선택 정렬)
ex) 3’ 7 3 2 5 로 시작할때, 첫 번째 회전 후 2 7 3 3’ 5로 바뀐다. 때문에 Unstable하다.
Quick Sort(퀵 정렬)
ex) 3 5 5 1 3 2 2 5 로 시작할때(가운데 3이 피벗)
첫 번째 회전 후, 3 2 5 1 3 2 5 5 으로 바뀌기 때문에 Unstable하다.
Heap Sort(힙 정렬)
동일한 노드 값이 양 옆에 있는 상황에서 6이 제거 된 경우에서, 왼쪽 7(2)올라 가기 때문에 Unstable하다.