[알고리즘] 안정 정렬 vs 불안정 정렬 (Stable Sort vs Unstable Sort)

https://cuffyluv.tistory.com/123 이전에 작성한 글 참고. 

data = [(1, 3, 5, 7, 9), (1, 3, 2, 4, 8), (2, 2, 3, 6, 7), (3, 1, 6, 8, 10)]
result = sorted(data, key=lambda x: (x[1], x[0]))
print(result) # [(3, 1, 6, 8, 10), (2, 2, 3, 6, 7), (1, 3, 5, 7, 9), (1, 3, 2, 4, 8)]

위와 같은 파이썬 코드가 있다.

튜플을 요소로 가지는 리스트에서, 각 요소를 정렬할 건데,

첫 번째 정렬 기준을 튜플의 두 번째 요소,

그리고 위의 첫 번째 정렬기준이 일치할 경우, 튜플의 첫 번째 요소를 정렬 기준으로 하여서 정렬하는 코드이다.

 

그러면, 튜플의 두 번째 요소와 첫 번째 요소가 일치할 경우, 즉 정렬 우선순위가 동일한 두 요소가 있을 경우,

해당 두 요소는 어떻게 정렬될까?

즉, 위의 예시에 있는 `(1, 3, 5, 7, 9)과 `(1, 3, 2, 4, 8)`는 튜플의 두 번째 요소와 첫 번째 요소가 모두 동일한데,

이 둘끼리는 어떻게 정렬될까?

 

정답은 기존의 순서인 `(1, 3, 5, 7, 9), (1, 3, 2, 4, 8)`를 유지한다.

파이썬의 `sorted()` 함수는 `안정 정렬(stable sort)`인 `팀소트(Tim sort)`로 구현되어 있기 때문이다.

---

안정 정렬(Stable sort)

- 같은 우선순위를 가지는 것끼리는 기존의 정렬 순서를 유지하는 정렬.

안정 정렬의 예시

- 병합 정렬(Merge Sort)

- 버블 정렬(Bubble Sort)

- 삽입 정렬(Insertion Sort)

- 계수 정렬(Counting Sort)

- 팀 소트(팀 정렬, Tim sort) 

불안정 정렬(Unstable sort)

- 같은 우선순위를 가지는 것끼리 기존의 정렬 순서를 유지하지 않을 수 있는 정렬.

 

* 오해1: 같은 우선순위를 가지는 것끼리 랜덤으로 섞는 게 아님!!

=> 각 알고리즘에 따라 같은 우선순위인 것들 순서 처리 방식은 차이가 있음.

 

* 오해2: 무조건 기존의 정렬 순서를 유지하지 않는 게 아님!!

=> 기존의 정렬 순서대로 나올 수도 있음.

 

- 즉, 정렬 과정에서 자연스럽게 기존 순서가 보장되지 않을 뿐인거지, '랜덤'하게 바뀌는 게 아님.

- 항상 순서가 바뀌는 것은 아니지만, 바뀔 가능성이 있는 것. (물론 일반적으로는 바뀔 가능성이 더 높겠지?)

불안정 정렬의 예시

- 퀵 정렬(Quick Sort)

- 힙 정렬(Heap Sort)

- 선택 정렬(Selection Sort)

---

파이썬의 경우

- 파이썬의 `sorted()`와 `list.sort()`는 내부적으로 팀 소트를 사용해 구현되어 있어, 안정 정렬이다.

- 또한, `max()` 함수도 (안정 '정렬'이라고 할 순 없지만) 비슷하게 안정적(stable)이어서, 같은 우선순위를 가지는 인자가 있으면 먼저 등장한 인자를 선택한다.

before = "apple"
now = "grape"
result = max(before, now, key=len)
print(result) # apple

- 위는 그 예시. 길이가 같은 두 인자에 대해, 먼저 온 인자 before이 반환된 것을 볼 수 있다.

- 아래 Ref.에 파이썬 공식 문서를 읽어보길 추천.

---

Ref. 

https://docs.python.org/ko/3.13/library/functions.html#sorted

https://docs.python.org/ko/3.13/library/functions.html#max