각각 10 비트로 표시되는 거대한 정수 배열 정렬

Question

이와 같은 문제 - 각 정수가 10 비트로 표현되는 정수 배열을 정렬하려면 어떻게해야합니까? 저는 counting sort를 사용할 수 있다고 생각합니다. 그러나 정수와 문자열의 조합 인 각 항목의 문제를 약간 조정하면 정수 값을 기준으로 배열을 정렬하라는 질문을 어떻게 해결할 수 있습니까?

Answer 1

여전히 빈 정렬 계산과 같은 정렬을 사용할 수 있습니다. 여전히 1024 개의 저장소가 있지만 그 저장소를 유지하는 대신 각 저장소는 해당 정수 키가있는 문자열 목록을 보유합니다.

필요한 경우 각 bin의 문자열을 개별적으로 정렬 할 수 있습니다. 이를 위해 quicksort와 같은 비교 정렬이 가장 좋습니다.