다음 시나리오를 생각해보십시오 : 10Mb의 정수 배열이 읽기 전용 저장 매체에 저장되어 있습니다. 숫자를 오름차순으로 인쇄하고 싶습니다. 그러나, 나는 단지 2 MB의 메인 메모리 (그리고 하드 디스크가 없다)를 가지고있다.제한된 메모리 및 읽기 전용 디스크로 정렬
매우 간단한 O (n) 솔루션 (사용 가능한 주 메모리를 사용하지 않음)은 전체 입력 배열을 반복적으로 스캔하여 다음 가장 작은 정수를 점진적으로 출력하는 것입니다. 내가 더 나은 정렬 알고리즘에 대한 인터넷 검색을 시도했지만 해답은 읽기 전용 스토리지 제약으로 인해 작동하지 않는 내부 또는 외부 정렬 알고리즘으로 안내합니다. 더 나은 해결책이 있습니까?
주 메모리를 사용하면 주어진 관계의 크기로 스캔 횟수를 줄일 수 있습니다.
첫 번째 스캔 : 지금까지 발견 된 가장 작은 숫자로 거의 주 메모리 크기의 메모리 내장 스토어를 유지하십시오. 저장소가 아직 가득 차 있지 않은 경우 배열에서 읽은 다음 번호를 추가하십시오. 상점이 가득 차면 상점의 가장 큰 수와 비교하여 새 상점이 더 작은 경우 가장 큰 수를 제거하고 새 수를 추가하십시오. 전체 배열이 스캔되면 순서대로 찾은 숫자를 출력하고 저장된 최대 수 및이 청크에서 얼마나 자주 발생했는지 기억하십시오.
이후 검색 : 스캔 된 숫자가 이전 청크에서 가장 큰 숫자와 같고 해당 발생 횟수가 이전 스캔 횟수보다 작 으면 발생 횟수를 증가 시키되 발생 횟수는 증가 시키되 매장에 추가하지는 않습니다 발생 횟수가 기억 된 횟수보다 크거나 같으면 저장소에 번호를 추가합니다 (필요한 경우 저장소에서 가장 큰 번호 제거). 스캔 한 번호가 이전 스캔의 가장 큰 번호보다 크지 만 저장소의 최대 번호보다 작은 경우 (또는 저장소가 아직 가득 차 있지 않은 경우) 저장소에 추가합니다 (필요한 경우 가장 큰 번호 제거). 스캔이 완료되면 저장된 번호를 순서대로 출력하고 지금까지 출력 된 가장 큰 번호와 총 출력 된 번호를 기억하십시오 (가장 큰 숫자는 이전 스캔의 번호와 같을 수 있으므로 지금까지 처리 된 모든 청크에서 얼마나 자주 출력되는지를 아는 것).
저장소에 대한 최상의 데이터 구조는 무엇인지 모르겠지만 힙이 좋은 선택이 될 수 있다고 생각합니다 (O (로그 크기), 최종 정렬 출력 : O (크기 * 로그 크기), 이진 검색 트리에서와 같이 메모리 오버 헤드가 거의 없습니다.
배열이나 제한된 범위에 중복 정수가없는 것과 같은 다른 제약은 없습니까? – Kwariz
이들은 32 비트 정수이며 중복이 허용됩니다. – del