정렬 알고리즘의 안정성(Stability)

오늘은 정렬 알고리즘의 안정성(Stability)에 대해 알아보겠습니다!

 

지금까지 매우 다양한 정렬 알고리즘들을 소개해 보았는데요

이러한 정렬 알고리즘에서 정렬이 얼마나 빨리 가능한지 속도(시간복잡도) 측면이 제일 중요하지만

또 다른 기준인 안정성(Stability) 또한 중요합니다

 

# 안정성(Stability) 이란?

정렬 전후 값이 동일한 데이터들의 순서가 동일한지 여부를 의미하는데요

안정적인(Stability) 정렬 알고리즘은 동일한 값의 데이터가 정렬 전후에 원래의 순서를 유지하는 반면.

안정적이지 않은(Unstability) 정렬 알고리즘은 동일한 값의 데이터가 정렬 전후에 순서가 바뀌게 됩니다!

 

예) 3_a, 2, 3_b, 5, 3_c 1, 7 

7개의 값을 오름차순으로 정렬하려고 합니다 (3인 중복된 값이 3개 존재)

 

안정적인(Stability) -> 1, 2, 3_a, 3_b, 3_c , 5, 7

안정적이지 않은(Unstability) -> 1, 2,3_b,3_a,3_c, 5, 7

안정적이지 않은 정렬의 경우, 동일한 3의 값의 위치가 변경되었습니다

 

그렇다면 안정적인 정렬 알고리즘, 안정적이지 않은 정렬 알고리즘은 무엇이 있을까요?

 

# 정렬 알고리즘의 안정성 구분

안정적인(Stability)

-> 삽입정렬(Insertion), 버블정렬(Bubble), 병합정렬(Merge), 기수정렬(Radix), 계수정렬(Counting)

 

안정적이지 않은(Unstability) 

-> 선택정렬(selction), 쉘정렬(Shell), 퀵정렬(Quick), 힙정렬(Heap)

 

# 안정성을 고려하는 이유?

키-값(보조정보) 쌍으로 이루어진 요소들을 정렬시 보조정보 순서 변형

동일한 키임에도 불구하고, 다른 값인 데이터의 경우 Unstability 정렬 알고리즘의 경우 정렬 후 위치가 변경됩니다

즉, 보조정보는 순서가 바뀌게 됩니다!

 

불필요한 교환 작업 발생

Unstability 정렬 알고리즘의 경우 교환과정에서 불필요한 교환 연산이 발생하므로 비효율적입니다

교환하려는 값들이 매우 많은 정보를 가지고 있는 경우, 교환시에  더 많은 자원을 요구하게 됩니다