안정적인 정렬이 중요한 차이를 만드는 확실한 예 (또는 비즈니스 사용 사례)

Question

안정적인 정렬이 큰 영향을 줄 수있는 시나리오를 알고 싶습니다.

이전 버전의 Java에는 Array.sort, quicksort에 대한 안정적인 정렬 인 collections.sor API에 대한 병합 정렬이 있습니다. Java의 현재 버전은 Tim Sort를 사용합니다. Tim Sort는 다시 안정적인 정렬입니다. 요즘 Python, Java, Scala와 같은 인기있는 언어가 Tim Sort를 사용하고 있습니다. Tim Sort가 안정적으로 사용되는 데 얼마나 큰 영향을 미치는지 알고 싶습니다. 안정적인 정렬 기술을 사용하는 강력한 동기는 무엇입니까?

Answer 1

안정적인 정렬을 사용하면 한 번에 한 필드 씩 데이터 세트를 최하위에서 최상위까지 정렬 할 수 있습니다. 예를 들어 일부 스프레드 시트 프로그램은 한 번에 3 개 필드 씩 정렬하는 데 한계가 있습니다. 스프레드 시트 정렬이 안정적이므로 6 개의 필드 정렬이 가능합니다. 먼저 가장 중요하지 않은 3 개의 필드별로 정렬 한 다음 3 개의 가장 중요한 필드별로 정렬합니다. 원래 순서를 유지하면 원하는 부작용이 될 수 있습니다. 데이터 세트가 이름순으로 정렬 된 다음 해당 데이터 세트의 사본이 생년월일로 정렬되고, 동일한 생년월일의 요소는 복잡한 이름 비교없이 원래 이름 순서를 유지합니다.

빠른 정렬과 병합 정렬에 대한 성능 문제가 있습니다. 일반적으로 병합 정렬은 움직임이 많지만 비교는 적습니다. 비교 오버 헤드가 이동 오버 헤드보다 크면 병합 정렬이 빨라집니다. 예를 들어, 객체에 대한 포인터 배열을 정렬하면 (자바가 객체 배열을 어떻게 구현하는지) 병합 정렬이 더 빠를 수 있습니다. 이동되는 것은 포인터이고 비교 대상은 객체입니다.