floating-point - 浮動小数点データの基数ソート

Question

基数はどのように float データをソートしますか? たとえば、12.4、45.13 など。小数点の右側を最初に読み取るか、小数点の左側を最初に読み取るか、小数点の右側を読み取った場合、数値をどのように処理しますか?それは最初に右端を最初に読みますか？

score 2 · Accepted Answer

それについての議論のこのページを参照してください。

基本的に、コンピューターは浮動小数点を特定の形式で格納します。彼らはそれを 45.13 とは書きません。その結果、そのように考えても、実際の動作には関係しません。

それを無視すると、基数ソートは最初に最も重要な部分を見る必要があります。浮動小数点数では、左端の桁です。基本的に、小数点の前の桁数が同じになるようにすべての数値をパディングします。次に、数字を左から右に読み取ります。

score 1 · Accepted Answer

基数ソートは、数値の 2 進表現で動作し、オブジェクトを 2 進整数であるかのようにソートします。

実際の整数と文字列の場合、バイナリ表現は私たちが期待する照合順序と非常によく一致するため、基数ソートは興味深い代替手段ですが、多少変わっています。

浮動小数点数が正しい方向に走査される限り、符号ビットを逆に処理することを除けば、基数ソートはうまく機能することがわかります。

内部バイナリ表現では、FP 値には符号ビット、約 10 ビットの指数があり、約 20 または 50 ビットが「小数」または仮数です。

S E E E E E E E E M M M M M M M M M M M M M M M . . .

指数は、小さい値が実際には最も負の指数になるようにバイアスされているため、仮数と同様に正しくソートされます。

すべての数値が正または負のいずれかである限り、または符号ビットが最初に反転され、スキャンが左から右である場合、基数ソートは FP 数値で機能すると思います。

score 0 · Accepted Answer

3 に答える 3