stable sort : 우선 순위가 같은 데이터들은 어떻게 정렬될까요?

 stable sort는, 정렬 알고리즘을 논할 때 간과하고 넘어가기 쉬운 키워드입니다. 하지만, 간과해서는 안 되는 것입니다. 이것이 대체 무엇을 의미할까요? 우선순위가 같은 데이터가 여러 개 있을 때, 정렬이 끝난 후에도, 순서가 유지되는 정렬을 stable sort라 합니다. 그렇지 않다면 unstable하다고 합니다.

 

 

---

 예제를 하나 봅시다. n개의 데이터를 정렬한다고 해 봅시다. 매 회전마다 [i,e] 구간에 있는 원소들을 탐색해서, 가장 우선순위가 높은 원소가 있었던 위치를 lo라고 해 봅시다. 이 때 lo와 i에 있는 원소를 뒤바꾸는 정렬이 있다고 해 봅시다.

 

 

 위에 있는 숫자는 숫자, 밑에 있는 숫자는 정렬 전 위치라고 해 봅시다. 만약에 숫자를 오름차순 정렬한다고 하면, 1이 0보다는 우선 순위가 낮을 것입니다. 1회전일 때, [1,3] 구간에 있는 원소들을 탐색합니다. 가장 우선순위가 높은 원소는 0입니다.

 

 

 그러면 이 친구랑 0번째 원소를 바꿔야 할 겁니다.

 

 

 이 시점에서, 우선순위가 같지만 순서가 뒤틀어졌습니다.

 

 

 원래 0번째 위치에 있었던 {1, 0}은, 1번째 위치에 있었던 {1, 1}보다 앞에 있었습니다. 그런데, 1회전 후에 이 둘의 위치가 바뀌어 버렸습니다. 이 상태로 계속 2회전, 3회전을 진행해 보도록 합시다.

 

 

 [2, 3]에 있는 원소들 중에서 우선순위가 제일 높은 것은 1입니다. 2번째에 있는 원소 또한 1이기 때문에, swap이 되지 않습니다. 3회전으로 가 봅시다.

 

 

 [3, 3]에서, 우선순위가 제일 높은 것은 1입니다. 3번째에 있는 원소는 1이기 때문에 swap 되지 않습니다. 최종적으로, 0번째에 있었던 1과, 1번째에 있었던 1의 순서가 바뀌었습니다. 즉, stable sort가 아니라는 겁니다.

 

 

---

 반대로, 저번 시간에 배웠던 삽입 정렬은 어떤가요?

 

 

 현재 내가 넣어야 할 원소를 x라고 합시다. 오름 차순으로 정렬한다고 했을 때, x보다 큰 최초의 위치를 찾을 겁니다. 그러면 같은 x라도, 정렬하기 전에 lo보다 작은 위치에 있었던 것들은 모두 연두색에 있었을 겁니다. lo번째에 있었던, 원소를 넣기 전에요.

 

 오른쪽으로 1칸씩 이동이 되는 것은 빨간색으로 칠한 부분입니다. 따라서 stable 합니다. 한 가지 더 질문을 하도록 합시다. STL의 sort는 어떨까요?

 

 

 moo 구조체에 2개의 필드를 넣습니다. 하나는 x, 그러니까 실값입니다. 2번째는 lo, 그러니까 정렬 전에 어느 위치에 있었는지를 나타내는 변수입니다.

 

 

 여기서 저는 arr[i].x의 값을 모두 0으로 같게 했습니다. 다른 것은 lo값일 겁니다. 즉, 배열 안에 있는 원소들의 우선순위는 모두 같습니다. 이 때, 정렬 후에 순서가 유지되는지 볼까요? 유지되는지 보려면, i<j라면, arr[i].lo보다는 arr[j].lo가 더 커야 할 겁니다.

 

 

 실제로 정렬 후에 arr[i-1].lo > arr[i].lo인 경우를 모두 찍어보았습니다. 666672번째에 있었던 0이, 666657번째에 있었던 0보다 앞에 등장했습니다. 정렬 전에는 666672번째에 있었던 0이, 666657번째에 있었던 0보다는 뒤에 있었을 겁니다. 우선순위가 같은 데이터에 대해서 정렬 전과 후에 순서가 유지가 되지 않았다는 의미입니다. 우선 순위가 같은 데이터에 대해서, 정렬 전과 후의 순서를 유지하게 하기 위해서 stable_sort 라는 함수를 씁니다.

 

 

 17번째 줄이, sort 대신에 stable_sort로 바뀌었습니다. 정렬 후에, 저는 arr[i].lo의 값을 출력하라고 했습니다.

 

 

 순서가 그대로 유지됨을 알 수 있어요. 우선순위가 같은 데이터들에 대해서 정렬 전과 후에 순서가 변하지 않았다는 것입니다. 이러한 특성을 가지면, 해당 정렬은 stable 하다고 이야기 합니다.