ソートアルゴリズムの安定性—平等の扱い

アルゴリズムはコンピュータサイエンスの中心です。ソートに使用されるアルゴリズムは、最も基本的で有用なものであり、その結果、ユビキタスです。

アルゴリズム—特定の問題を解決するための明確なステップの有限集合。

私たちは常に無意識のうちにグループ化されたオブジェクトの順序を並べ替えて依存しています。たとえば、優先度に従ってリスト上のタスクをランク付けします。本は高さで棚に積み上げます。スプレッドシートまたはデータベースの行を並べ替えるか、辞書の単語のアルファベット順に依存します。時々、私たちは秩序だった配置である種の美しさを知覚することさえあります。

プログラマーとして、ソートされた配置がどのように見えるかに影響するため、ソート方法を知ることは重要です。すべてのソートが同じ方法でオブジェクトを並べ替えるわけではありません!このため、ソート操作の結果は、使用するアルゴリズムによって異なります。これが認められない場合、私たちは自分自身や私たちのソフトウェアを使用する人々を驚かせるかもしれません。

ソートアルゴリズムの安定性は、それらの間の際立った特性の1つです。これは、アルゴリズムが同等のソートキーを持つ比較可能なアイテムをどのように処理するかを扱います。

並べ替えキー—コレクション内のアイテムの順序を決定するために使用されるキー(年齢、高さ、アルファベットの位置など)。

安定したソートアルゴリズムは、等しいソートキーを持つアイテムの相対的な順序を維持します。不安定なソートアルゴリズムはそうではありません。つまり、コレクションが安定した並べ替えアルゴリズムで並べ替えられる場合、同じ並べ替えキーを持つアイテムは、コレクションが並べ替えられた後も順序を保持します。

例、コード、およびデモ

上の画像は、安定ソートの効果を示しています。左側では、データは名前のアルファベット順にソートされています。データを成績で並べ替えると、同じ成績の各行で名前のアルファベット順が維持されていることがわかります。

ソートが不安定な場合、上の画像に示すようにアルファベット順が維持される保証はありません。

必ずしも安定したソートは必要ありません

使用するソートが安定しているかどうかを知ることは特に重要です。特に、データに別の並べ替えキーで並べ替えるときに維持したい順序がすでにある場合は特にそうです。たとえば、スプレッドシートには、デフォルトで名前で並べ替えられた学生データを含む行があります。また、名前の並べ替え順序を維持しながら、成績で並べ替えることもできます。

一方、コレクション内のオブジェクトの並べ替えキーがオブジェクト自体(整数や文字列の配列など)である場合は、複製の違いがわからないため、並べ替えの安定性は重要ではありません。キー。

// JavaScript
// $5 bucks if you can correctly tell which 4 in the sorted// array was the first 4 when the array was unsorted.
var numbers = [5, 4, 3, 4, 9];numbers.sort(); // [3, 4, 4, 5, 9]
// A one second trip around the world, courtesy of the Flash, to// whomever correctly tells me which 'harry' in the sorted array was// the second 'harry' in the unsorted array.
var names = ['harry', 'barry', 'harry', 'cisco'];names.sort(); // ['barry', 'cisco', 'harry', 'harry']

並べ替えはどこにでもあります—並べ替えを知っています

プログラミング言語またはライブラリのデフォルトのソートが安定しているかどうかを確認するのは非常に簡単です。ドキュメントにはこの情報を含める必要があります。たとえば、デフォルトの並べ替えはPythonでは安定しており、Rubyでは不安定で、未定義ですか?JavaScriptで(ブラウザの実装によって異なります)。

一般的な並べ替えアルゴリズムとその安定性を次に示します。

  • 挿入ソート—安定
  • 選択ソート—不安定
  • バブルソート—安定
  • マージソート—安定
  • シェルソート—不安定
  • Timsort —安定

より網羅的なリストについては、ウィキペディアを参照してください。

デモ時間ですか?‍?

このデモは、安定した(挿入ソート)および不安定なソート(選択ソート)アルゴリズムを使用して、データの小さなテーブルをソートした場合の効果を示しています。これを構築している間、私は少し楽しく、実質的にリバースエンジニアリングされたReactを持っていました。ソースを見てください。

次は何ですか?

If you are thirsty for more knowledge about the stability of other sorting algorithms, Wikipedia has a good comparison table and additional information on well known sorting algorithms.

Until next time, peace.

Learned something new or enjoyed reading this article? Clap it up ?, share it so that others can read too, and follow along for more. Feel free to leave a comment too.