먼저 정렬 알고리즘이란
주어진 데이터를 숫자나 사전 순서와 같이 일정한 기준에 따라 순서대로 재배열하는 절차
오늘날에는 많은 정렬 알고리즘이 있다. 그중에서도 이번 글에서는 sort중에서도 stable한 sort와 unstable한 sort를 알아볼려고 한다.
Stable Sort
우선 Stable한 sort는 뭘까?
간단히 말해서 같은 키값을 가진 노드들이 정렬 전이랑 정렬 후에도 같은 순서인 경우이다.
예를 들자면
(A, 3) - (B, 4) - (D, 1) - (C, 1)가 있다고하자.
이 값들을 두번째 키인 숫자로 오름차순으로 정렬한다고 해보자.
Stable한 정렬을 한다고 생각해보면
(D, 1) - (C, 1) - (A, 3) - (B, 4)가 와야될 것이다.
왜 이게 Stable한 걸까?
그 이유는 (D, 1) - (C, 1) 같은 키값에 순서가 바뀌지 않았기 때문이다.
Stable한 정렬 기법에 종류를 살펴보자면 대표적으로
-
Bubble Sort - 서로 인접한 값들을 비교하여 자리를 교환하는 방식인데 만약 값이 같다면 자리교환은 발생하지 않는다.
-
Merge Sort - 반으로 쪼개서 정렬 후 합병하는 분할 정복 기법이다. stable한 이유는 순서도 같이 보장해서 합병하기 때문이다.
Unstable Sort
이제 바로 Unstable이 뭔지 알아보자.
앞 설명을 들으면 대충은 예측할 수 있을 것이다.
키값이 같은 노드들이 정렬 전이랑 정렬 후랑 순서가 달라지는 경우이다.
같은 예시를 들어보자면
(A, 3) - (B, 4) - (D, 1) - (C, 1)가 있다고하자.
이 값들을 두번쨰 키인 숫자로 오름차순으로 정렬한다고 해보자.
Unstable한 정렬을 한다고 생각해보면
(C, 1) - (D, 1) - (A, 3) - (B, 4)가 와야될 것이다.
이제 바로 알수 있듯이 (C, 1)와 (D, 1)의 순서가 정렬 전과 바뀌었다.
Unstable한 정렬 기법에 종류도 살펴보자
-
Quick Sort - 피벗값을 기준으로 큰값과 작은값들을 분할하여 정렬하는 기법이다. Merge Sort와 다르게 순서보장이 안된다는 것이다. 그 이유는 피벗값과 같은 값을 가진 노드가 왼쪽으로 갈지 오른쪽으로 갈지에 대한 기준이 없다는 것이다.
-
Selection Sort - 값들에 나열에서 맨 앞자리에 최소값을 찾아서 바꾸는 정렬 기법이다. 이 기법에서 같은 키값이라도 최소값이랑 바꾸다보면 순서보장을 할 수가 없기때문이다.
그래서 왜 Stable이 중요한가?
흠... 내 생각으론 단순히 하나의 키값으로 정렬하는 기법에선 Unstable, Stable 둘중 어떤 거를 써도 상관없을 것 같다. 하지만 키값이 2개이상일 경우에는 Stable한 기법을 사용하는 게 좋아보인다. 왜냐하면 하나의 키값으로 Unstable한 기법으로 정렬해버리면 다른 나머지 키값에 대한 정렬에 순서가 망가지기 때문이다.
