Mergesort(4),(5) : comparators, stability

comparator는 comparable과 비교되는 자바의 인터페이스로 제가 이해하기엔 좀 어렵네요.

당장 자바로 알고리즘을 풀이할 것도 아니라서 과감히 패스하겠습니다!

 

Stability

• 때로는 정렬 기준(key)이 여러 개가 될 수도 있습니다.
  예를 들어 이름을 기준으로 정렬한 다음, 2번째 열의 숫자를 기준으로 정렬하고 싶을 수도 있다는 것이죠.
• 하지만 두 번째 열을 기준으로 정렬하는 순간 이름 기준의 정렬이 깨지는 것을 원하지 않을 수도 있습니다.
  즉, 두 번째 정렬을 수행하더라도 기존의 정렬이 유지되길 원하는 경우 어떻게 이를 구현할 수 있을까요?

 

Stability: insertion sort

• 삽입 정렬은 정렬이 수행되는 매 스텝(i)에서 이전에 정렬된 것들은 건드리지 않습니다.
  비교 대상이 더 작은 경우 swap을 멈추기 때문이죠.
  따라서 stable 정렬입니다.
• 합병 정렬이 stable 하려면 merge가 stable해야 합니다.
  이 정렬 역시 이전에 정렬된 원소를 건드리는 것은 아니고, 작게 쪼갠 배열의 정렬 결과를 합치는 방식이므로 stable한 알고리즘입니다.
• 결과적으로 합병 정렬은 시간 복잡도 측면에서도 가장 효율적이며 이전 정렬 결과를 보장할 수 있는 stable한 정렬 알고리즘입니다.

 

 

Stability: selection sort, shell sort

• 하지만 선택 정렬의 경우 이전에 정렬된 값을 재배치하는 경우가 존재합니다.
  따라서 선택 정렬은 unstable하다고 할 수 있습니다.
• shell sort도 같은 이유로 unstable합니다.

 

 

 

출처: Coursera, Algorithms, Part 1, Princeton University