データ構造の並べ替え方法の比較

ここでは、いくつかのソート方法を示します。 200以上のソート手法があります。それらのいくつかを見るでしょう。一部の並べ替え手法は比較ベースの並べ替えであり、一部は非比較ベースの並べ替え手法です。

比較ベースのソート手法には、バブルソート、選択ソート、挿入ソート、マージソート、クイックソート、ヒープソートなどがあります。これらの手法では、値が比較され、さまざまなフェーズでソートされた位置に配置されるため、これらの手法は比較ベースのソートと見なされます。ここでは、これらの手法の時間計算量を確認します。

一部の並べ替えアルゴリズムは、非比較ベースのアルゴリズムです。それらのいくつかは、基数ソート、バケットソート、カウントソートです。ここでは2つの要素が並べ替え中に比較されないため、これらは非比較ベースの並べ替えです。テクニックは少し異なります。ここで、さまざまなタイプの分析に基づいて、それらの違いを確認します。

ソート手法は、他のいくつかのパラメーターを使用して比較することもできます。一部の並べ替えアルゴリズムはインプレース並べ替えアルゴリズムであり、一部はアウトプレース並べ替えアルゴリズムです。余分なスペースを必要としないこれらのアルゴリズムは、インプレースソートアルゴリズムと呼ばれます。クイックソート、ヒープソートアルゴリズムなどが導入されています。ただし、マージソートはアウトプレースソート手法です。

一部のアルゴリズムはオンラインで、一部はオフラインです。ソートプロセスの進行中にアルゴリズムが新しい要素を受け入れる場合、それはオンラインソートアルゴリズムと呼ばれます。上記の手法から、挿入ソートはオンラインソート手法です。