Quicksort를 stable sorting이 되게 하는 법

2021.04.17 - [알고리즘] - stable sort, unstable sort 개념, 정렬방식 정리/ quick sort, selection sort는 stable한가?

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

이전 포스팅을 통해 quicksort는 stable sort가 아니라는 것을 알아보았다. 만약 quick sort를 stable sorting으로 바꾸고 싶다면 어떻게 할 수 있는지 의문이 들 수 있다. 

 

위의 포스팅에서도 알 수 있겠지만 quick sort가 stable sorting이 되지 않는 이유는 swap을 하는 과정에서 숫자의 위치가 바뀔 수 있기 때문이다. 따라서 이렇게 swap을 하지 않게, 배열의 왼쪽부터 검사를 한다면 quick sort를 stable sorting으로 바꾸어줄 수 있다. 대신 하나의 배열이 추가적으로 필요하다. 즉 추가적인 공간복잡도를 감수한다면 quick sort도 stable sorting으로 바꿔줄 수 있는 것이다.

---

구체적인 방법을 알아보자. 

예시로 위와 같은 배열이 있다고 가정해보자. 그리고 pivot 원소는 가장 마지막 원소인 5라고 가정해보자.

그런 뒤에 새로운 배열 두 개를 만들어 준다.

위 노란색 배열은 pivot 원소보다 작은 원소를 담아줄 배열이고,

위 파란색 배열은 pivot원소보다 크거나 같은 값을 담아줄 배열이 되는 것이다. 

 

이후 왼쪽 index부터 하나씩 보면서 pivot 원소인 5보다 작은 원소는 노란색 배열에, 5보다 큰 원소는 파란색 배열에 담아준다. 

 

그러면 아래와 같이 담아지는 것을 알 수 있다.

이후, 그러면 노란색 배열의 원소를 차례로 담고, 그 다음의 pivot 원소인 5, 이후 파란색 배열의 원소를 차례로 담아주면 4 4 5 7 8 이런식으로 정렬이 잘 되는 것을 알 수 있다. 

 

여기서 중요한 점은 이렇게 quicksort를 변형한 방법은 stable sorting이 된다는 것이다. 노란색 배열의 4 4 원소는 기존 원소의 순서를 파괴하지 않은 채로 잘 반영이 되었다. 이는 기존 quick sort에서 swap을 하는 방법을 사용하지 않고 배열의 왼쪽부터 검사를 하면서 배열을 나누어 담았기 때문이다.

 

이 방법의 장점은 stable sorting이 된다는 점이지만 단점은 space complexity가 좋지 않다는 점이다. 위에서 볼 수 있듯이 추가적인 배열이 더 필요하다는 단점이 있다. 

 

결론은 구현 방식에 따라 약간의 변형에 의해 quick sort도 stable sorting으로 바꿀 수 있다는 것이다.