정렬 알고리즘을 공부하다 보니, stable / unstable 이나 in-place와 같은 용어들이 등장했다. 학교 수업에서 배웠던 기억은 나는데 정확히 알고 있다는 느낌을 받지 못했고, 헷갈리는 지점들도 있어서 정리한다.
Stable
- stable한 정렬이라는 의미는 중복된 요소를 정렬할 때 초기 배열에서 주어진 순서를 유지하는 정렬을 의미한다!
- 이 의미는 알고 있었지만, 왜 쓰는지에 대해서는 고민이 부족했다. 이번 기회에 생각해봤다.
stable, unstable을 구별하는 이유(뇌피셜)
- 우선 숫자로만 이루어진 배열을 정렬할 때는 stable, unstable을 구별해서 사용하는 것이 의미가 없다고 판단했다. ex) [1,25,3,6,3,3]
- 하지만 배열의 요소가 복합적으로 구성되어 있고, 중복되는 key값을 가지는 요소에 대해 원래 순서를 유지해야하는 상황이라면
Stable Sort를 해야한다.
# 주문 목록을 처리할 때, 수량이 작은 주문부터 처리하고,
# 수량이 같을 경우에는 들어온 순서대로 처리해야하는 상황을 가정해보자.
# 배열 => [(수량, 이름)]
arr = [(10, "김시환"), (3, "이수지"), (4, "임연수"), (3, "이다연")]
배열의 요소의 첫번째 요소를 기준으로 정렬!
이경우에 Unstable sort를 사용하면 원하는 결과값을 얻지 못할 수도 있다!
Stable Sort를 사용하면 항상 원하는 결과값을 얻을 수 있다!
따라서 Stable Sort를 사용하는 것이 합리적이다.위와 같은 가상 상황을 고려해봤을 때, Unstable Sort를 사용하면, 중복된 Key를 갖는 요소들의 이전 순서를 보장하지 못한다. 그러므로 추가적인 (비효율적인) 확인 과정이 필요하다.
정렬을 해야하는 문제 상황이 주어지고, 목표에 따라서 정렬 알고리즘을 선택할 수 있는 기준 중 하나로 Stable/Unstable 이 사용된다고 결론내렸다.
In-place
in-place 정렬은 원소들의 개수에 비추어 봤을 때 무시할만한 추가 공간을 사용하거나, 추가 공간을 사용하지 않는 정렬 알고리즘이다.
in-place sort가 필요한 이유
가장 처음 생각할 수 있는 이유는 공간 복잡도에서 이득이다. 그럼 공간이 충분할 경우에는 in-place sort인지 아닌지가 중요하지 않다는 결론이 나오는데 뭔가 찝찝해서 인터넷 서칭을 했다.
내가 읽은 블로그 글에서는 in-place sort를 쓰는 이유를 공간 지역성 때문이라고 말한다.
메모리를 할당받을 때, page 단위로 할당받는다. 추가적인 공간을 사용한다는 것은 연속적이지 않은 메모리를 사용한다는 말이다. in-place sort를 했을 때는 배열의 요소들이 연속적인 메모리 상에 올라가 있을 것이다. 하지만, 그렇지 않은 정렬은 추가적인 메모리를 할당받는데, 이때 이 메모리들은 연속적이지 않다. 따라서 In-place sort의 공간 지역성이 좋다. 이를 통해 캐시의 성능을 높일 수 있기 때문에 성능적으로 차이가 날 것이다.
굉장히 합리적인 이유를 찾은 것 같다. 한 수 배웠다.
