배포 정렬 (기수 정렬 등)을 사용하여 문자열을 정렬하는 방법은 무엇입니까?

Question

기수 정렬을 사용하여 정수를 정렬하는 방법을 알고 있습니다.

그러나 문자열을 정렬하는 데 어떻게 사용합니까? 또는 부동 소수점 숫자?

Answer 1

무한대, 숫자가 아닌 값 및 두 개의 다른 표현과 같은 일부 특성을 무시하면 기수 정렬 또는 기타 다른 배분 정렬을 사용하여 부동 소수점 숫자를 정렬 할 수 있습니다. IEEE 754-2008 부동 소수점 숫자는 정수로 정렬 순서가 호환되는 이진 표현을 갖습니다. 따라서 숫자가 아닌 숫자를 제외하고 float 또는 double을 int32 또는 int64으로 재 해석하면 모든 분포 유형을 직접 적용 할 수 있습니다. 편집 : 음수 부동 소수점 숫자는 정렬 순서가 정수의 정렬 순서와 반대이므로 특수 처리 (AShelly에서 지적한 바와 같이)가 필요합니다.

문자열의 경우 가변 길이 때문에 문자열이 더 어려워집니다. 다른 종류의 분배 정렬 (버킷 정렬)이 사용될 수 있으며 종종 문자열에 사용됩니다. 문자열의 여러 시작 문자가 버킷 색인화에 사용되며 비교 정렬을 사용하여 버킷 내부의 문자열을 정렬합니다.

모든 문자열의 길이가 거의 같거나 일부 기법이 문자열 간의 차이를 증폭하는 데 사용되는 경우 (예 : "FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs"의 6 장 참조) 기수 정렬을 사용할 수도 있습니다. 문자열을 문자 그룹 또는 더 나은 비트 그룹으로), 같은 그룹을 정수로 재 해석하고 정수의 기수 정렬 인 것처럼 계속 수행하십시오.

편집 : 모든 종류의 배포 정렬은 ASCII 문자열의 경우에만 올바르게 작동합니다. 다른 문자열 인코딩에는 다른 정렬 순서가 필요할 수 있으며 로캘의 "조합"매개 변수에 따라 달라질 수 있습니다.

Answer 2

예 가능합니다.

플로트에 대해서는 Radix Sort, Sorting a float data을 참조하십시오. 정수 타입으로 캐스팅 된 부동 소수점이 정확하게 비교된다 (일단 음수가 정정되면). 자세한 내용은 this article을 참조하십시오.

문자열의 경우 MSD 기수 정렬을 수행하고 Null이 발생할 때 내림차순을 중지하여 가변 길이 문제를 해결할 수 있습니다. Radix sort implemented in c++ for string을 참조하십시오.