Algorithm 4 - Stability & In-place sorting

 In-place & Stability property

- In-place
sorting 과정에서 추가적인 공간이 필요하지 않고 (변수 할당 등의 공간을 제외하고) output 결과를 input 메모리 공간에서 그대로 생성 가능한 것.
이 방법은 메모리 공간이 한정되어 있을 때 사용하기 편리하다.

- Stability
같은 크기(key)를 가지는 element가 있을 경우, sorting 후에도 해당 element들의 순서가 변하지 않는 것. 이는 원소들이 여러 개의 key로 분류 가능하고, 단계별로 sorting 할 때 중요하게 고려해야 한다.

일반적인 숫자들의 sorting에는 이들이 서로 구별가능한 또다른 key가 없기 때문에 (크기를 제외하고) 별로 상관없지만, 년-월-일 등으로 구성되는 날짜 데이터의 경우, 년, 월, 일의 순서대로 오름차순 정렬 할 수 있다. 이 때 stability가 존재해야 원하는 정확한 결과를 얻을 수 있다. (stability가 보장되지 않는다면 여러 개의 key를 사용하여 sorting 하였을 때 올바르지 않은 결과를 얻을 수도 있음)


상기 기준에 따라 기존 sorting 방식을 비교해보면 Bubble sort와 insertion sort는 in-place & stable 알고리즘이라는 것을 알 수 있다. (insertion은 하나씩 선택하여 sorted 위치의 앞과 뒤와 모두 비교하므로 같은 것이 있을 경우 순서가 변하지 않는다)

그러나 selection sort의 경우, 두 원소를 선택하여 위치를 바꾸기 때문에, in-place 이기는 하지만, stable하지는 않다. (최소 원소와 교환 과정에서 동일 key 원소들의 상대 위치가 바뀔 수 있음)

Merge sort는 divided sub array를 놓을 장소가 필요하기 때문에 in-place 하지 않다. (input size와 동일한 크기의 sub array가 필요 - big O(n) )
stability의 경우, merge 방식에 따라 달라질 수 있지만 stable 하게 생성할 수 있으므로 일반적으로 stable로 고려한다.  (left sub을 항상 combined의 왼쪽에 놓는 방식을 선택할 경우 stable 하다.)

Quick sort는 pivot을 기준으로 두 부분으로 나누게 되므로 in-place 이다. 그러나 selection sort의 경우와 동일하게, big/small sub array의 element를 교환하거나 pivot을 올바른 위치에 넣을 때 교환을 이용하여 넣게 되므로 동일 원소가 있을 때 순서가 바뀔 수 있다.