[이론] Stable Sort

Stable sort란

중복된 키를 순서대로 정렬하는 정렬 알고리즘을 지칭한다. 즉 같은 값 2개 이상이 리스트에 등장할 때, 기존 리스트에 있던 순서대로 중복된 키들이 정렬된다는 것을 의미한다.

numbers = [9, 3, 12, 1, 6, 2, 2]
↓
numbers = [9, 3, 12, 1, 6, 2(첫번째), 2(두번째)]
↓
[1, 2(첫번째), 2(두번째), 3, 6, 9, 12]

위 예시를 살펴보면 이해가 쉽다. 이처럼 기존 리스트에서 중복된 값들에게 순서가 매겨졌는데, 그 순서대로 정렬이 됐을 때 이 알고리즘을 stable sort라고 부를 수 있다.

​

Stable sort의 중요성

• Stable sort로 정렬하는 알고리즘들의 순서는 항상 똑같기에 같은 결과를 보장한다
• 숫자를 정렬할 때 stability가 중요하지 않을 수 있지만, 첫 문자를 기준으로 문자열을 정렬하는 경우에는 항상 안정적으로 같은 리스트가 리턴된다. (정렬할 때마다 순서가 다르면 난장판이 될 것)

Stable sort 예시

• Insertion sort
• Merge sort
• Bubble sort
• Counting sort