algorithm - すべてのカテゴリの線形時間ソート

Question

私はこの多分愚かな考えを持っていました

カウントソート、基数ソートを使用して、整数などの制約されたカテゴリの線形時間ソートアルゴリズムがあるためです。

コンピュータ ワードのように、数値型のすべてのカテゴリは最終的にバイト シーケンスにエンコードされます (整数などとある程度似ています)。これらの線形時間ソートアルゴリズムを使用して、これらすべての数値に対して線形時間ソートを行うことができると述べることができますか?

Answer 1

確かに、詳細はタイプごとに異なりますが。簡単な例の1つは、IEEE-754浮動小数点値（32ビットと64ビットの両方）です。これは、整数であるかのようにほとんど並べ替えることができます。（より具体的には、それらは符号の大きさの整数であるかのようにソートできます。）したがって、基数ソートは正常に機能します。

文字列の場合、メモリに収まらないほど多くの文字列がある場合の珍しいことではない手法は、さまざまな基数ソートであるプレフィックスによって文字列を「ビン化」することです。

短いビットフィールド値（整数や上記の浮動小数点数など）の場合、左から右への基数ソートは、基本的にはクイックソートの単なる変形であるため、実際にはクイックソートの変形にすぎません。もっともらしいピボットを見つけます。クイックソートとは異なり、有限の再帰深度（32ビット値の場合は32）が保証されます。一方、データセットサイズのlog ₂は通常32よりはるかに小さいため、クイックソートの再帰深度は通常はるかに小さくなります。

クイックソートの主な利点は、2つの値を比較する関数を呼び出す方法を除いて、ソートされるデータ型について何も知らなくてもアルゴリズム（STLスタイル）を記述できることです。基数ソートについても同じことは言えません。汎用バージョンを作成するのは非常に困難です。

1つの重要なポイントを追加するために編集：

O（n）とO（n log n）の違いを強調しすぎるのはよくあることです。nが非常に大きい場合、それらは異なります。ただし、実際のGoogle以外のサイズの問題のほとんどでは、lognは小さな整数です。log nが50より大きい場合を除いて、 2n log ₂ n秒かかるO（n log n）アルゴリズムがある場合、100n秒かかるO（n）アルゴリズムを使用することは意味がありません。 nは1,125,899,906,842,624より大きかった。

Answer 2

いいえ、あなたがすることはできません。以下のバイトで表されるデータがある場合：

11001100 00110011
(204)    (51)

基数ソートのようなものを使用してこれらをソートすると、次のようになります。

00110011 11001100
(51)     (204)

これに関する唯一の問題は、これがディスクに書き込んだデータではなく、まったく別のデータであり、まったく意味がない可能性があることです（ゴミ）。