[알고리즘] stable sort 와 unstable sort

 

 

초안 : 2021년 9월 22일

1차 수정 : 2023년 4월 10일

 

기존 Sort(정렬) 알고리즘들이 여러 가지가 있다. 그중에서도 크게 2가지로 나눌 수가 있는데, 바로 

Stable Sort와 UnStable Sort로 나눈다.

우선 Stable와 UnStable의 사전적 의미로는 아래와 같다.

 

 

https://search.naver.com/search.naver?where=nexearch&sm=top_hty&fbm=0&ie=utf8&query=stable+

 

 

https://search.naver.com/search.naver?sm=tab_hty.top&where=nexearch&query=unstable&oquery=stable&tqi=hRr6xwprvN8ss4ypRjRssssstMd-393082

 

정렬 알고리즘의 stability란, 동일한 키(key) 값을 가진 원소(element)들이 정렬 후에도 서로의 상대적인 위치가 유지되는 성질을 말합니다. 따라서 stable 한 정렬 알고리즘은 같은 값을 가진 원소들의 순서가 보존되어야 하는 경우에 유용합니다.

 

 

안정적인(stable) 정렬과 불안정한(UnStable) 정렬로 해석이 되는데, 먼저 안정적인 정렬은 나열된 수를 정렬한 뒤에도 기존에 있던 순서를 유지하는것이 Stable Sort이고, 정렬한 다음에 기존 순서를 유지하지 않는다면 UnStable Sort이다.

 

 

대표적인 Stable Sort로 

- Insertion Sort (삽입 정렬)
- Bubble Sort (버블 정렬) 
- Merge Sort (병합 정렬) 
- Heap Sort (힙 정렬)
- Quick Sort (퀵 정렬) 
- Selection Sort (선택 정렬) -> 

이 있다.

 

그리고 UnStable Sort로는 

- Counting Sort (계수 정렬) 
- Radix Sort (기수 정렬)
- Bucket Sort (버킷 정렬)

들이 있다. 하지만 어떤 정렬 알고리즘은 구현방식에 따라 UnStable <-> Stable 해질 수 있다는 점이 있다.

 

실질적으로 내가 적용하는 알고리즘을 볼 때,Stable해지는지 UnStable 해지는지 잘 구분해야 할 것 같다.

 

 

 

위의 정렬알고리즘들 중 일부를 정리한 글이다.

https://hyo-ue4study.tistory.com/68

[알고리즘]정렬 알고리즘의 선택과 종류 7가지