정렬 a, b, c는 정렬 c와 같습니다. 정렬 b; 정렬?

Question

C++에서는 데이터 집합의 사용자 지정 정렬을 허용하는 "Excel/Access와 비슷한"(견적) 쿼리 작성기를 구현해야합니다. 쿼리 작성기 또는 SQL에서 "ORDER BY a, b, c"를 사용하여 Excel에서 열 A, B 및 C별로 정렬하면 순서대로 모든 As를 얻고 순서대로 동일한 각 그룹 내의 모든 Bs를 얻습니다. 각 그룹 내의 모든 C를 순서대로 정렬합니다. 이는 대부분의 사람들이 "a, b, c로 정렬/정렬"하여 이해하는 것입니다. 이것은 "c로 정렬"을 수행 한 다음 "b로 정렬"을 수행 한 다음 "정렬 기준"으로 처리하는 것과 같습니다. 즉. 역순으로 각 열에 개별적으로 정렬 - stable_sort를 사용하는 한. 내 프로그램에서 어떻게 구현했는지. 사용자가 "sort by a, b, c"라고 말하면 프로그램은 stable_sort를 c, stable_sort를 b, stable_sort는 같은 결과로, 지금까지 사용했던 모든 데이터 세트를 사용합니다. 내 질문은이 안정적인 정렬 알고리즘을) 및 모든 열의 조합을 사용하는 모든 데이터 집합 (제공되는 잘 알려진 동등한이며, 거기에 대한 수학적 증거도 무엇입니까? Google이나 다른 방법 (프로그래머, 통계 학자 및 수학자에게 묻기)을 통해 그러한 증거를 찾지 못했습니다.

Answer 1

네, 맞습니다.

정렬 알고리즘은 동일한 키를 가진 두 개의 레코드 R과 S가 있고 원본 목록의 S 앞에 R이 나타나는 경우 안정적입니다. R은 항상 정렬 된 목록에서 S 앞에 나타납니다.

b에 정렬 한 후 a에 정렬하여 "b에 의해 다음, a을 기준으로 정렬"을 구현하는 알고리즘을 고려하십시오. 첫 번째 정렬 (b)은 정렬 알고리즘 (안정성은 이 아니며 첫 번째 정렬에 대한 요구 사항이이 아님)보다 높은 b이있는 레코드보다 먼저 낮은 b 인 모든 레코드를 남겨 둡니다.

두 번째 정렬 (a)은과 동일 할 때만 b에주의해야합니다. 안정적인 덕분에이 정렬은 정렬 전과 동일한 순서로 - 즉 b 순으로 동일한 a의 레코드를 남겨 둡니다. 이것은 정확히 a, 그 다음에 b 순으로 정렬 할 때 달성 한 것입니다.

더 많은 정렬 단계를 추가하면 이전 단계의 결과가 원래 순서대로 유지된다는 것을 관찰함으로써 동일한 증명이 두 개 이상의 키를 기준으로 정렬까지 확장 될 수 있습니다. 정확하게 동일한 그룹 내에서 원하는 순서입니다 더 높은 정렬 우선 순위를 갖는 키.