[알고리즘] - 안정 정렬(Stable Sort)과 불안정 정렬(Unstable Sort) #2

저번 포스팅에서 언급했듯이 정렬에 대해서 알아보도록 하겠습니다.

우선 정렬 알고리즘을 배우기 전에 정렬의 안정적 특성에 대해서 알아야 할 필요가 있습니다.

이 특성을 모르고 정렬 알고리즘을 선택한다면, 우리가 원하는 결과를 얻지 못할 수 있기 때문입니다.

정렬의 안정적 특성이란?

정렬의 안정적 특성이란 "정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지되느냐" 입니다.

이러한 정렬의 안정적 특성에 따라서 정렬 알고리즘은 안정 정렬과 불안정 정렬로 구분 할 수 있습니다.

예를 들어, 아래와 같은 포커 카드에 대해서 번호를 키값으로 하여 오름차순으로 정렬하고자 합니다

이때, 우리는 약간 이상한 성향으로 인해(?) 같은 숫자카드의 무늬 순서를 유지시키고자 합니다.

즉, 아래 그림의 경우 정렬 후에도 하트4 뒤쪽에 스페이스4가 위치하게 하고 싶다는 의미입니다.

"당연히 유지되는게 정상 아니야?" 라고 생각 하실 수 있지만, 정렬 알고리즘에 따라서 정렬 후에 이 순서가 바뀔 수도 있습니다.

안정 정렬(Stable Sort) 

안정 정렬의 경우에는 정렬 후에도 원래의 순서가 유지되며, 결과는 다음과 같습니다.

정렬된 결과에서 하트4와 스페이스4의 순서가 그대로 유지되고 있음을 확인 할 수 있습니다.

불안정 정렬(Unstable Sort)

불안정 정렬의 경우에는 정렬 후에도 원래의 순서가 유지된다는 보장을 할 수 없으며, 결과는 다음과 같을 수 있습니다.

안정 정렬의 결과와는 달리 스페이스4와 하트4의 순서가 바뀐 모습을 확인 할 수 있습니다.

 

앞으로 배울 정렬 알고리즘에는 안정 정렬 알고리즘도 있고, 불안정 정렬 알고리즘도 있습니다.

따라서 이를 구분해서 학습을 해야 합니다. 너무 걱정하지는 마세요! 정렬 알고리즘을 설명할 때 같이 하도록 하겠습니다.

이번 포스팅은 여기까지며 다음 글부터 본격적으로 정렬 알고리즘에 대해서 알아보도록 하겠습니다!