データ構造-ソート手法

並べ替えとは、特定の形式でデータを配置することです。並べ替えアルゴリズムは、特定の順序でデータを配置する方法を指定します。最も一般的な順序は、番号順または辞書式順序です。

並べ替えの重要性は、データが並べ替えられた方法で保存されている場合、データ検索を非常に高いレベルに最適化できるという事実にあります。並べ替えは、データをより読みやすい形式で表すためにも使用されます。以下は、実際のシナリオでの並べ替えの例の一部です。

Telephone Directory −電話帳には、名前でソートされた人の電話番号が格納されているため、名前を簡単に検索できます。
Dictionary −辞書には単語がアルファベット順に格納されているため、任意の単語を簡単に検索できます。

インプレースソートと非インプレースソート

ソートアルゴリズムでは、いくつかのデータ要素の比較と一時的な保存のために、追加のスペースが必要になる場合があります。これらのアルゴリズムは余分なスペースを必要とせず、ソートはインプレースで、またはたとえば配列自体の中で行われると言われています。これはin-place sorting。バブルソートは、インプレースソートの例です。

ただし、一部のソートアルゴリズムでは、プログラムはソートされる要素以上のスペースを必要とします。等しいかそれ以上のスペースを使用するソートはと呼ばれますnot-in-place sorting。マージソートは、インプレースソートの例です。

安定ソートと不安定ソート

ソートアルゴリズムは、コンテンツをソートした後、それらが表示される類似のコンテンツのシーケンスを変更しない場合、それは呼び出されます stable sorting。

ソートアルゴリズムが、コンテンツをソートした後、それらが表示される類似のコンテンツのシーケンスを変更する場合、それは呼び出されます unstable sorting。

アルゴリズムの安定性は、たとえばタプルのように、元の要素のシーケンスを維持したい場合に重要です。

適応型および非適応型のソートアルゴリズム

ソートされるリスト内のすでに「ソートされた」要素を利用する場合、ソートアルゴリズムは適応型であると言われます。つまり、ソースリストにすでに並べ替えられている要素がある場合に並べ替えるときに、適応アルゴリズムはこれを考慮に入れて、それらを並べ替えないようにします。

非適応アルゴリズムは、すでにソートされている要素を考慮しないアルゴリズムです。彼らは、すべての要素を強制的に並べ替えて、並べ替えを確認しようとします。

重要な用語

いくつかの用語は、一般的にソート手法を議論するときに造られます。ここにそれらの簡単な紹介があります-

注文の増加

値のシーケンスはにあると言われています increasing order、連続する要素が前の要素よりも大きい場合。たとえば、1、3、4、6、8、9は昇順で、次のすべての要素が前の要素よりも大きいためです。

注文の減少

値のシーケンスはにあると言われています decreasing order、連続する要素が現在の要素よりも小さい場合。たとえば、9、8、6、4、3、1は降順です。これは、次のすべての要素が前の要素よりも小さいためです。

増加しない注文

値のシーケンスはにあると言われています non-increasing order、連続する要素がシーケンス内の前の要素以下の場合。この順序は、シーケンスに重複する値が含まれている場合に発生します。たとえば、9、8、6、3、3、1は昇順ではありません。これは、次のすべての要素が（3の場合）以下であるが、前の要素よりも大きくないためです。

非減少注文

値のシーケンスはにあると言われています non-decreasing order、連続する要素がシーケンス内の前の要素以上の場合。この順序は、シーケンスに重複する値が含まれている場合に発生します。たとえば、1、3、3、6、8、9は降順ではありません。これは、次のすべての要素が前の要素以上である（3の場合）ためです。