並べ替えアルゴリズムと数値間の距離

Question

長いlong unsigned intで配列が配列されているとします。隣接する要素間の距離は小さい。たとえば、次のようになります。[0,1,0,1,0,1] 別の配列が同じサイズであり、隣接する要素間の距離が重要になりました。 次に、[1、1000000000、1、1000000000、1、1000000000]という配列があります。

最後のステップは、挿入ソートまたはマージソートまたはクイックソートで2つの配列をソートすることです。 要素間の距離が離れているため、2番目の配列の処理時間が長くなる可能性はありますか？

ありがとうございます！彼らはこれらの要素ではなく、それらの絶対サイズの相対順序に純粋に基づいて要素をソートするため、挿入ソート、クイックソート、およびマージソート等

Answer 1

ソートアルゴリズムは、比較ソートと呼ばれます。 quicksort、mergesort、または挿入ソートの観点から、配列[0,1,0,1,0]と[0,100000,0,100000,0]は完全に同一です。なぜなら、100000 「1よりもはるかに大きい」。これらの配列をソートするために実行される操作の総数は、完全に同じになります。実際に、これらのアルゴリズムで各配列をソートし、要素が動き回るのを見ると、まったく同じ動きが行われることがわかります。

1つの機械語に収まる整数をソートする場合、移動のコストはその機械語に格納されている数値とは関係ありません。これらの要素を比較するコストも同じである可能性があります。したがって、これらのアルゴリズムでこれらの配列をソートするのに必要な時間には全く違いはないと私は予測しています。

異なる場合は、使用しているプロセッサが異なるサイズの数を異なる時間数で比較または移動できることを意味します。私の知る限りでは、これを行う実際のプロセッサーアーキテクチャーはありません。

さて、一方、比較ソートではなく、ソートまたは基数ソートを数えるようなアルゴリズムを、ソートはは、これらをソートするために時間がかかる可能性があり、あなたが扱っている数字の大きさに依存を行います一度に1桁の数字で作業するか、質問内の数字のサイズに応じたサイズの配列に分配することによって、配列を作成できます。そのような場合、はになります。使用したアルゴリズムがうまく実装されていれば、ランタイムの違いを確認できます。