[Stable Sort(안정 정렬) vs Unstable Sort(불안정 정렬)]

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(힙 정렬)

 

 

출처:https://blog.naver.com/zephyehu/150013176075

동일한 노드 값이 양 옆에 있는 상황에서 6이 제거 된 경우에서, 왼쪽 7(2)올라 가기 때문에 Unstable하다.