불안정정렬

Last updated - 2023년 04월 25일 Edit Source

불안정 정렬 (Unstable 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보다 앞에 있음을 보장하지 못한 것이다.

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