[ Algorithm ] 정렬 알고리즘의 안정성

정렬 알고리즘의 안정성

• safety가 아니라 stable이다.
• 똑같은 key를 가진 데이터들의 순서가 바뀌지 않느냐의 여부

안정성이 중요한 이유

똑같은 값이 바뀌는게 문제가 없다고 생길 수도 있지만, 버그가 생길 수도 있다.

안정성을 잘 모르는 이유

• 같은 키를 가진 데이터의 순서가 바뀌어도 문제가 아닌 경우가 보통

• 그래서 잘 모르고 생각을 안하는 경우가 많음

• 심지어는 이렇게 잘못 생각하기도 함

  • '모든 정렬 알고리즘은 같은 키를 가진 데이터의 순서를 안 바꾼다.'

• 이 때문에 버그가 나도 못 고치는 경우가 있음

• 팩트

  • 어떤 정렬 알고리즘은 안정성을 보장
  • 어떤 정렬 알고리즘은 보장하지 않음

안정성이 문제가 되는 경우

1. 정렬의 기준이 되는 정렬 키(sort key)와 실제 데이터가 다름

2. 구조체/클래스의 일부 멤버만 정렬 키로 사용