In - Place와 Stability 소개

In Place

In - Place 정렬 알고리즘이란, input data를 정렬하기 위해 각 요소들을 옮기는 과정에서 output을 내기 위해서 추가적인 공간이 필요하지 않은 알고리즘을 말한다.

이것을 설명하기 위한 딱 맞는 알고리즘이 있다. Merge sort를 생각해보자.

 

우리는 아주 잘게 배열들을 나눠서 merge하는 정렬을 사용했었다. 그런데 이 과정에서 왼쪽 공간의 배열과 오른쪽 공간의 배열을 합치며 정렬할 때, 추가적인 메모리를 갖는 temp array를 선언해서 그 장소에 따로 저장을 했었다.

그렇게 두 배열을 temp array에 합치고 나서 원래의 배열에 다시 복사하여 할당했지만.. 아무튼 Merge sort의 경우 정렬을 할 때 extra space가 필요하므로 In - Place 알고리즘이 아니라고 말할 수 있다.

 

반대로 배열을 정렬함에 있어서 추가적인 메모리 공간이 따로 필요하지 않은 알고리즘을 In - Place 알고리즘이라고 말한다. 사실상 merge sort를 제외한 지금까지 배운 모든 알고리즘이다.

 

 

Stability

우리가 정렬 알고리즘에 input data를 넣었을 때, 그 출력 결과로 나온 data가 input과 같은 순서로 정렬된 경우
우리는 Stable하다고 말한다. 솔직히 말로만 했을 땐 잘 와닿지 않는다.

이 그림과 같이 배열 안에는 같은 값을 갖는 요소가 있을 수 있다. 만약 알고리즘을 통해 정렬이 된 후에도 n개의 서로 동일한 값의 요소가 input될 때의 순서와 같다면 stable하다고 말한다.

 

일단 뭐.. 알겠는데 이런 개념이 정렬에 필요할까?

싶었는데 생각보다 많이 쓰이고 유용했다. 주로 multiple key를 갖는 정렬에서 사용된다.

이것은 Year과 Month의 키 두개를 갖는 정렬이다.

우선 Month를 순서대로 정렬시킨 후, 이 정렬이 깨지지 않도록 Year 순서대로 다시 정렬시킨다.

이렇게 하면 각각 년도가 같은 값을 갖더라도 stable하기 때문에 Year 정렬에선 이미 정렬된 month는 신경쓰지 않아도 된다.

 

 

---

 

 

이제 우리가 지금까지 배웠던 알고리즘들의 in place와 stability를 따져보자.

 

우선 bubble sort다.

버블정렬은 자신과 인접한 element의 순서가 잘못됐으면 swap을 반복하는 알고리즘으로, 정렬에 추가적인 공간이 따로 필요하지 않고 stable하다. 방금 말했다싶이 순서가 잘못된 경우만 swap하기 때문이다..

아까 in place에 대해 설명할 때 merge sort 말고 다른 알고리즘은 정렬할 때 추가적인 메모리 공간이 필요하지 않다고 말했었다. 다음 알고리즘부터 in place는 그냥 생략하겠따...

 

 

다음으로 selection sort는 각 회차마다 아직 정렬되지 않은 element들을 순회하며 가장 작은 수를 변수 min에 저장하는 것을 반복한다. 그런데 아직 정렬되지 않은 부분을 scan하는 도중, min에 있는 값과 서로 동일한 값을 발견할 경우 원래 배열의 순서를 보장할 수 없기 때문에 이것은 unstable한 알고리즘이다.

 

 

Insertion sort는 아직 정렬되지 않은 부분에서 정렬된 부분으로 반복해서 Key를 삽입한다. 이미 정렬된 부분은 건드리지 않기 때문에 이 알고리즘은 stable하다.

 

 

Merge sort는 input 리스트를 반으로 나눈 다음, 반으로 나눈 각각의 리스트를 merge sort를 사용하여 재귀적으로 정렬한다. 아까 말했듯이, 합치는 과정에서 extra space가 필요하기 때문에 in place한 알고리즘이 아니다. 그리고 extra space에 저장하는 방식이 왼쪽 배열을 먼저 저장하기 때문에 순서를 보장할 수 있어서 stable한 알고리즘이다.

 

 

Quick sort는 pivot을 기준으로 pivot보다 작으면 왼쪽 index에, 크면 오른쪽 index에 하나씩 저장한다.
이 알고리즘은 기존의 순서에 상관 없이 왼쪽 오른쪽 index에 다 때려박기 때문에 순서를 보장하지 않으므로 unstable하다.

 

 

이 내용들을 표로 정리하자면 아래와 같다.