配布ソート（基数ソートなど）を使用して文字列をソートするにはどうすればいいですか？

Question

私は基数ソートを使って整数をソートする方法を知っています。

しかし、それを使用して文字列をソートする方法はありますか？または浮動小数点数ですか？

Answer 1

無限大、数値でない値、2つの異なるゼロ表現などのいくつかの特性を無視すると、基数ソートやその他の分布ソートを使用してソートすることができます。 IEEE 754-2008浮動小数点数はバイナリ表現を持ち、整数でソート順に互換性があります。したがって、数字以外を除外してfloatまたはdoubleをint32またはint64と再解釈すると、それらに直接配布ソートを適用できます。 編集：負の浮動小数点数は、ソート順が整数のソート順とは逆のため、特別な処理（AShellyで指摘されているように）が必要です。

文字列では、可変長なので難しくなります。他の種類のディストリビューションソート（バケットソート）が使用され、しばしば文字列に使用されます。文字列のいくつかの開始文字がバケットインデクシングに使用され、比較ソートが使用されてバケット内の文字列をソートします。

文字列の違いを増幅するために、すべての文字列の長さがほぼ等しい場合は、radixソートを使用することもできます。文字列を文字のグループに分割します（例："FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs"）これらのグループを整数として再解釈し、整数の基数ソートのように続行します。

編集：すべての種類の配布タイプは、ASCII文字列に対してのみ正しく動作することが保証されています。他の文字列エンコーディングは、異なるソート順を必要とするか、ロケールの "照合"パラメータに依存することがあります。

Answer 2

はい、可能です。

フロートについてはRadix Sort, Sorting a float dataを参照してください。浮動小数点型の整数型へのキャストが正しく比較されます（ネガが訂正された後）。詳細については、this articleを参照してください。

文字列の場合、MSD基数ソートを行い、NULLに遭遇したときに下降を止めることで、可変長問題を解決できます。 Radix sort implemented in c++ for stringを参照してください。