stable sort, unstable sort 개념, 정렬방식 정리/ quick sort, selection sort는 stable한가? : Programming Story

1. Stable Sort, Unstable Sort란?

stable sort란 sorting을 할 경우에 같은 값의 숫자더라도 그 상대적인 위치가 유지되는 sorting 방식이다. 예를 들어

3 3 4 2 1 5 3

예를 들어 위와 같은 배열을 sorting 한다고 했을 때,

그 결과값이

1 2 3 3 3 4 5

이런식으로 유지된다면 stable sorting이라고 할 수 있다. 색깔을 잘 보면 이해가 될 것이다. 즉 같은 원소더라도 원래의 순서가 sorting 후에도 유지되면 stable sorting, 유지되지 않으면 unstable sorting이라고 할 수 있다.

2. Sorting 방법에 따른 stable sort 여부 정리

그러면 각각의 sorting 방법에 따라 stable sorting인지를 확인해보자

결론부터 말하면 quicksort와 heapsort는 unstable sorting이며, selection sort는 어떤 식으로 구현하는지에 따라 stable이 될 수도 있고 안될수도 있으며, 나머지 insertion sort, merge sort, bubble sort는 stable sorting이라고 할 수 있다.

1) quicksort

https://www.programmingstory.com/2024/02/quick-sort-pivot.html

quicksort에 대한 설명은 위의 포스팅에서 이미 다루었다.

quicksort 가 stable sorting이 될 수 없는 이유는 예를 들어 1, 1, 1, 5, 2, 3, 4 같은 것만 예시로 해 보아도 알 수 있다. pivot 원소보다 작거나 같은 것이 있으면 i를 하나 늘리고 A[i]와 A[j]를 바꾸기 때문에 앞의 같은 1이 연속적으로 나오면서 stability가 훼손된다.

2) heapsort

만약 max-heap으로 구현되었다고 치고 40 30 30 20 10을 heapsort로 sorting한다고 해보자. 그러면 40이 가장 뒤로 가고 앞에 있는 30이 먼저 제거되어 뒤로 보내지게 된다. 따라서 앞에 있는 30이 뒤에 있는 30보다 더 뒤로 가는 결과를 초래한다. 그러므로 heapsort도 unstable sorting이다.

3) selection sort

selection sort는 구현하는 방식에 따라서 달라진다. 만약 최대값을 구할 때 같은 원소이더라도 가장 뒤에 나오는 값을 최대값으로 구현한다면 stable sort라고 할 수 있다. 하지만 대부분 최대값을 구하는 방법이

가장 첫번째 원소를 최대로 놓고 그것보다 크다면 최대값을 update하는 식이기 때문에 많은 곳에서 stable sort가 아니다라고 말한다. 하지만 만약 내가 첫번째 원소를 최대로 놓고 그것보다 '같거나 크면' 최대값을 update한다면 selection sort도 stable sort가 될 수 있다.

4) bubble sort

대표적인 stable sort 중 하나이다. 뒤의 값이 앞의 값보다 작다면 두 값을 바꾸는 것이기 때문에 만약 같은 값의 경우에는 순서가 바뀌지 않는다.

5) insertion sort

insertion sort도 stable sort이다. 왜냐하면 자신보다 큰 값들에 대해서만 index를 하나씩 증가시키고 그 자리에 말 그대로 insert를 하는 sorting이기 때문이다. 만약 이것도 자신보다 크거나 같은 값에 대해 구현한다면 unstable로 만들 수 있다. 하지만 거의 대부분의 경우 그렇게 구현하지 않으므로 stable sorting이라고 알고 있으면 된다.

6) merge sort

stable sorting 방식이다. 대신 조건으로, 두 그룹 A, B를 merge 할 경우, 같은 값이 나온다면 앞의 그룹의 숫자를 먼저 가져다 써주어야 한다. 만약 그렇지 않으면 merge 중에 stability가 훼손될 것이다.

7) counting sort

counting sort에 대해 알고리즘 구현 방식을 찾아보면 오른쪽에서 왼쪽으로 scan을 하면서 output array에다가 다시 적어주는 형식이다. 마지막 for loop의 순서가 오른쪽에서 왼쪽 (array에서 n-1부터 0까지) 으로 구현되기 때문에 stable sorting이라고 할 수 있다.