Stable sort / Unstable sort

Stable sort
동일한 정렬기준을 가진 것은 정렬하기 전의 순서와 정렬한 후의 순서가 동일하다.

Unstable sort
동일한 정렬기준을 가진 것의 순서가 다를 수 있다.



알고리즘 때 배운 용어이다. 역시 머리가 안되니 까먹는다. 정렬할 때 동일한 정렬기준을 가진 것들이 많으면 어떤 것을 앞에 놓아야할지 고민하게 된다. 자.. 아래에 있는 숫자들을 숫자 크기의 오름차순으로 정렬해 보자.

5, 3, 4, 1, 4, 2, 3

결과는 "1, 2, 3, 3, 4, 4, 5" 가 될 것이다. 여기에 "3"과 "4"는 1개 이상이 존재한다. 이 "3"과 "4"의 순서가 정렬 이전의 순서대로 정렬되는 것을 보장한다면 stable sort, 그렇지 않고 다를 수 있다면 unstable sort가 된다. "3"과 "4"가 똑같아보이니 숫자에 색을 입혀서 정렬해 보자.

5, 3, 4, 1, 4, 2, 3

1개 이상 있는 "3"과 "4"는 빨간색과 파란색으로 표시를 하였다. 이 숫자를 정렬하였을 때 stable sort라면 꼭 다음과 같은 결과가 나와야 한다.

1, 2, 3, 3, 4, 4, 5

정렬하기 전에 "빨간 3"은 "파란 3"보다 앞에 있었으므로, 정렬 후에도 "빨간 3"은 "파란 3"보다 앞에 있어야 한다. 역시 "파란 4"도 "빨간 4"앞에 있어야 한다. 이렇게 정렬 전의 순서와 정렬 후의 순서가 동일함을 보장하는 것이 stable sort 이다. 만일 "빨간 3"과 "파란 3"의 순서가 바뀔 수 있다면 unstable sort이다. 다음은 unstable sort로 정렬한 한 예이다. unstable sort는 여러 결과가 나올 수 있다. 여기서는 "4"의 순서가 뒤바뀌었다.

1, 2, 3, 3, 4, 4, 5

- 단어 검색 동기
Web Search Personalization via Social Bookmarking and Tagging
by Michael G. Noll and Christoph Meinel

- 출처
stable & unstable sort 에 대하여