안정정렬

Last updated - 2023년 04월 25일 Edit Source

안정 정렬 (Stable Sort) : 중복된 값이 있는 경우, 입력 순서와 동일하게 유지하여 정렬하는 알고리즘

• 두 값이 같을 때, 이 때 값이 입력된 순서대로 정렬된다면 안정 정렬이다.
• 대표적으로 버블정렬, 삽입정렬, 합병정렬

ex) $(k_i,e_i), (k_j, e_j)$에 대하여 $k_i = k_j$이며 $i < j$였을 때, 정렬 이후에도 $i < j$라면 안정 정렬 알고리즘

• 하트 5와 스페이드 5를 보면 중복된 숫자이다.
• 정렬 전, 하트 5가 스페이드 5보다 앞에 위치
• 정렬 후, 하트 5가 스페이드 5보다 앞에 위치
• 즉, 안정정렬이 되려면 정렬이 되고 나서도 하트 5가 스페이드 5보다 앞에 있음을 보장해야하는 것이다.

• 초기에 입력값은 시간 순으로 정렬된 상태
• 입력 값을 지역별로 정렬하려는 상태
• 초기 입력된 순서가 시간 순으로 정렬되어 있다는 의미
  • 안정 정렬은 정렬 이후에도 입력 받은 순서를 보장해줌
    • 같은 지역을 보면 여전히 시간 순서로 정렬되어있음
  • 불안정 정렬은 무작위로 섞이기 때문에 입력받은 순서를 보장하지 못함
    • 같은 지역을 보면 시간 순서로 정렬이 되어있을수도, 아닐수도 있음