N 개의 정렬되지 않은 그룹으로 부분 정렬하는 효율적인 알고리즘

Question

다음을 수행하는 효율적인 알고리즘을 찾고 있습니다. N 개 항목의 배열이 주어지면 항목이 M 개의 동일한 그룹으로 올 수 있도록 정렬합니다. 각 그룹은 다음과 같습니다. 정렬되지 않지만 그룹은 서로간에 정렬됩니다 (한 그룹의 모든 요소는 다음 그룹의 요소보다 작음).

가장 쉬운 방법은 전체 배열을 정렬하는 것입니다. 그러나 특히 그룹 수가 총 항목 수보다 훨씬 적은 경우 (예 : 백만 개의 항목을 5 개 그룹으로 분류) 비효율적입니다.

현재 배열을 2 개의 정렬되지 않은 그룹으로 정렬 한 다음 M-1 번 적용하는 quickselect 알고리즘 (특히 Floyd-Rivest variation)을 사용하여 해결했습니다. 중요한 개선점은 quickselect에 divide-and-conquer 접근법을 적용하여 배열을 두 그룹으로 정렬 한 다음 각 그룹을 M 그룹으로 분류 할 때까지 정렬하는 것입니다. 일반적인 종류의 unordered partial sorting 문제입니다.

그러나 문제에 대한보다 간단하고 효율적인 접근 방법이 있다고 생각합니다. 제가 빠진 것이 있습니까? 어떤 아이디어? 내 RBush JavaScript library (효율적인 R * 트리 구현)에서 대량 삽입 성능을 향상시키기 위해이 기능이 필요합니다.

Answer 1

다음은 문제의 재 설명입니다. M-1 등급의 요소를 동시에 찾아 배열을 M 개의 정렬되지 않은 그룹으로 나눌 필요가 있습니다.

중간 크기에 가까운 임의의 피벗을 사용하여 표준 quickselect로 시작하는 것이 좋습니다 (임의의 서브 샘플 트릭으로 추정). 각 경우에 대해 배열을 2로 나누고 도 순위 목록을 나눕니다. 당신은 2로 또한 찾아내는 것을 요구하는 성분. 현재 그룹에서 순위가 ​​매겨진 요소가있는 레벨로 내려갈 때까지이 작업을 계속하십시오. 그런 다음 Quickselect의 Floyd-Rivest 변형으로 전환하여 실제로 그 요소를 찾고 현재 그룹을 2로 분할하십시오. 그런 다음 quickselect에서 다시 나오면 원하는 M 그룹을 쉽게 조각 낼 수 있습니다.

이 접근법은 꽤 좋은 상수로 O(N log(M))의 예상 실행 시간을가집니다. 나는 그것보다 훨씬 더 잘할 수 있는지 의심 스럽다.