MergeSort 구현 안정성

Question

mergesort 구현이 안정성에 영향을 줍니까?

예를 들어 배열을 사용하여 병합 정렬을 구현하는 경우 병합 정렬의 연결된 목록 구현보다 안정성이 낮습니까?

Answer 1

배열 또는 연결된 목록의 병합 정렬에 대한 상향식 (재귀 적) 및 상향식 (반복적) 구현의 대부분의 구현이 안정적입니다. 가장 중요한 요소는 병합 기능입니다. 병합 기능이 "오른쪽"요소 앞에 "왼쪽"요소를 움직이면 안정적입니다. 비교는 "왼쪽"요소 < = "오른쪽"요소 일 수도 있고 C++ 표준 라이브러리의 경우 비교를 위해 사용하는 것보다 적을 수도 있습니다. 비교는 "오른쪽"요소 < "왼쪽"요소이므로 "왼쪽"요소 < = "right"요소 인 경우 이동합니다.

다른 가능한 문제는 작은 그룹의 요소에 비 안정적인 정렬 방법을 사용하는 혼합 병합 정렬과 관련이 있습니다.

일반적으로 인접 요소를 스왑하는 정렬 (예 : 버블 정렬)은 일반적으로 안정적이지만 인접하지 않은 요소 (예 : 빠른 정렬)를 스왑하는 정렬은 일반적으로 안정적이지 않습니다.

Answer 2

병합 정렬은 둘 다 안정해야합니다. 당신이 목록이나 배열을 사용하면 무엇을 사용하고 있는지에 따라 다릅니다.

Answer 3

배열의 등가 키를 사용하여 요소의 상대 순서를 유지하면 정렬 방법이 안정적입니다.

위에서 아래로와 아래 위로 구현은 모두 안정적인 접근 방식입니다. 배열 또는 링크 된 목록과 독립적입니다.