並べ替えアルゴリズムはプログラミングで非常に広く使用されていますが、プログラマーはどのアルゴリズムが最適かを考えさえしない場合があります（「最適」という用語は、書き込みと実行の両方の速度と複雑さの組み合わせを意味します）。
この記事では、見つけようとします。 最良の結果を保証するために、提示されたすべてのアルゴリズムは200要素の整数配列をソートします。 テストを実行するコンピューターには、AMD A6-3400M 4x1.4 GHzプロセッサー、8 GB RAM、Windows 10 x64ビルド10586.36オペレーティングシステムの特性があります。
この調査では、次のソートアルゴリズムが選択されました。
選択ソート -アルゴリズムの本質は、配列の最小要素を見つけて先頭に移動する際に、配列を最初から最後まで調べることです。 このようなアルゴリズムの複雑さはO（n2）です。
バブルソート -配列の最初の要素が2番目の要素よりも大きい場合、このアルゴリズムは2つの隣接する要素を入れ替えます。 これは、アルゴリズムがすべての未ソート要素をスワップするまで発生します。 このソートアルゴリズムの複雑さはO（n ^ 2）です。
挿入ソート -アルゴリズムは、要素を通過するときに配列をソートします。 各反復で、要素が取得され、配列の既にソートされた部分の各要素と比較されます。したがって、「その場所」を見つけ、その後、要素がその位置に挿入されます。 これは、アルゴリズムが配列全体を通過するまで発生します。 出力では、ソートされた配列を取得します。 このアルゴリズムの複雑さはO（n ^ 2）です。
クイックソート -アルゴリズムの本質は、配列を2つのサブ配列に分割することです。中央の行は、配列の中心に位置する要素です。 アルゴリズムの操作中、平均よりも小さい要素は左に移動し、右に大きく移動します。 同じアクションがサブアレイから再帰的に発生し、カットするものがあるまで（1つの要素が残る）、さらに2つのサブアレイに分割されます。 出力では、ソートされた配列を取得します。 アルゴリズムの複雑さは入力データに依存し、せいぜいO（n×2log2n）になります。 最悪の場合、O（n ^ 2）。 平均値もあります。これはO（n×log2n）です。
櫛の並べ替え（櫛の並べ替え） -アルゴリズムの考え方は交換の並べ替えに非常に似ていますが、主な違いは、2つの隣接する要素が比較されるのではなく、ギャップ上の要素（5つの要素など）が比較されることです。 これにより、小さな値が最後に削除されないことが保証され、大きな配列でのソートを高速化するのに役立ちます。 最初の反復は、式（配列サイズ）/（削減係数）で計算されるステップで実行されます。削減係数は約1.247330950103979であるか、1.3に丸められます。 2回目以降の反復は、ステップ（現在のステップ）/（減少係数）で行われ、ステップが1に等しくなるまで続行されます。 ほとんどの場合、アルゴリズムの複雑さはO（n×log2n）です。
テストのために、各アルゴリズムの5回の起動が実行され、最適な時間が選択されます。 最適な時間とこれに使用されるメモリが表にリストされます。 また、10、50、200、および1000要素のサイズの配列を並べ替える速度をテストして、特定のアルゴリズムの対象となるタスクを決定します。
完全にソートされていない配列：
部分的にソートされた配列（要素の半分が順序付けられています）：
グラフで提供される結果：
結論：
調査と得られたデータの結果、ソートされていないアレイをソートするために、アレイをソートするために提示されたアルゴリズムの最も最適なものは高速ソートです。 実行時間は長くなりますが、アルゴリズムはより少ないメモリを消費します。これは大規模プロジェクトで重要になる可能性があります。 ただし、選択、交換、挿入による並べ替えなどのアルゴリズムは、たとえば大量のデータを処理する必要のないトレーニングなどの科学的な目的に適している場合があります。 部分的に並べ替えられた配列では、結果に大きな違いはありません。すべての並べ替えアルゴリズムの時間は約2〜3ミリ秒短くなります。 ただし、部分的に並べ替えられた配列を並べ替える場合、高速並べ替えははるかに高速に機能し、メモリの消費量が少なくなります。