データ構造-ソート手法

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

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

電話帳-電話帳には、名前で簡単に検索できるように、名前でソートされた人々の電話番号が格納されます。
辞書-辞書には単語がアルファベット順に保存されているため、単語の検索が容易になります。

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

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

ただし、一部のソートアルゴリズムでは、プログラムにはソートされる要素以上のスペースが必要です。同等以上のスペースを使用する並べ替えは、* in-in-place並べ替え*と呼ばれます。マージソートは、インプレースソートの例です。

安定したソートと不安定なソート

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

安定した並べ替え

コンテンツをソートした後、ソートアルゴリズムが表示される類似コンテンツのシーケンスを変更する場合、それは*不安定なソート*と呼ばれます。

不安定な並べ替え

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

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

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

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

重要な用語

いくつかの用語は、一般的に分類手法を議論する際に造られています、ここにそれらの簡単な紹介があります-

増加する順序

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

降順

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

非増加注文

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

非減少注文

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

Data-structures-algorithms-sorting-algorithms

目次