もしあなたがコンピュータサイエンスを専攻しているなら、挿入ソートはあなたが最初に耳にしたソートアルゴリズムの1つである可能性が高いです。
直感的で実装も簡単ですが、大きな配列では非常に遅く、ソートに使われることはほとんどありません。
挿入ソートは、ラミーをしながらカードの手札を並べ替えることに例えて説明されることが多い。
このゲームに馴染みのない方のために説明すると、ほとんどのプレイヤーは手札を昇順にソートして、どの組み合わせが自由に使えるかをすぐに確認できるようにしたいのです。
ディーラーは14枚のカードをあなたに配り、あなたはそれを1枚ずつ手に取り、正しい順番で手札に入れます。
この間、手札はソートされた「サブアレイ」となり、テーブル上の裏向きのカードはソートされていない状態なので、そこから一枚ずつカードを取り出して手札に入れます。
挿入ソートは非常にシンプルで直感的に実装できるため、プログラミングの初期段階で教えられることが多いのも理由の一つです。
安定したインプレースアルゴリズムであり、ほぼソートされた配列や小さな配列に対して非常に効果的である。
これらの用語について詳しく説明しましょう。
- インプレース。インプレース: (コレクションの入力サイズに関係なく)小さな一定の追加スペースを必要とするが、コレクション内の要素の元のメモリロケーションを書き換える。
- 安定。このアルゴリズムは、最初の配列から等しいオブジェクトの相対的な順序を維持する。つまり、あなたの会社の社員データベースが、2人の社員として「Dave Watson」と「Dave Brown」をその特定の順序で返すとする。もし、この二人を（共有の）ファーストネームでソートするとしたら、安定したアルゴリズムはこの順番が変わらないことを保証してくれるでしょう。
もう一つ注意すべき点は、挿入ソートはソートする前に配列全体をあらかじめ知っておく必要がないことです。
このアルゴリズムは一度に1つの要素を受け取ることができます。
このアルゴリズムは、ソートする要素をさらに追加したい場合に便利で、ソート全体を「やり直す」ことなく、その要素を適切な場所に挿入するだけです。
挿入ソートは小さな（～10個程度の）データセットに対して効率的であるため、実際にはかなり頻繁に使用されている。
これについては後で詳しく説明する。
挿入ソートの仕組み
挿入ソートの仕組み
配列は「ソート済み」部分配列と「ソートされていない」部分配列に分割されます。
ソートされた部分配列は、最初に元の配列の最初の要素だけを含んでいます。
ソートされていない配列の最初の要素は、ソートされた部分配列の適切な場所に挿入できるように、評価されます。
挿入は、新しい要素より大きいすべての要素を1つ右に移動することによって行われます。
>
配列全体がソートされるまで、この作業を続けます。
しかし、ある要素が他の要素より大きいとか小さいとかいう場合、必ずしも整数が大きいとか小さいとかいう意味ではないことに注意してください。
カスタムオブジェクトを使用する場合、「大きい」「小さい」という言葉は自由に定義できます。
例えば、点Aは点Bよりも座標系の中心から遠い場合、「大きい」と言える。
ソートされた部分配列に太字の数字を付け、次のような配列を使ってアルゴリズムを説明します。
8, 5, 4, 10, 9
まず、ソートされた部分配列に8を「追加」することになります。
8、5、4、10、9
ここで、最初のソートされていない要素である5を見てみましょう。
この値を別の変数、例えば current に保存して、安全に管理します。
5は8より小さいので、8を右に1つ移動させ、以前そこに格納されていた5を効果的に上書きします（そのため、安全のために別の変数に格納しています）。
となります。
5はソートされた部分配列のすべての要素より小さいので、最初の位置に挿入します。
5, 8, 4, 10, 9
となります。
となります。
次に4番を見てみましょう。
その値を current に保存します。
4は8より小さいので、8を右に移動し、5も同じようにします。
5, 5, 8, 10, 9 (current = 4)
ここでも、ソートされた部分配列全体よりも小さい要素に遭遇したので、それを最初の位置に配置します。
4、5、8、10、9
となります。
10はソートされた部分配列の一番右の要素より大きいので、8より左のどの要素よりも大きいです。
ですから、単純に次の要素に進みます。
となります。
9は10より小さいので、10を右に移動します。
4, 5, 8, 10, 10 (current = 9)
しかし、9は8より大きいので、単純に8の直後に9を挿入します。
4、5、8、9、10
実装
先に述べたように、挿入ソートは非常に簡単に実装することができる。
まずは単純な整数の配列に対して実装し、次にいくつかのカスタムオブジェクトに対して実装してみます。
実際には、オブジェクトを操作して特定の条件に基づいてソートすることの方がはるかに多いだろう。
配列の並べ替え
def insertion_sort(array):
# We start from 1 since the first element is trivially sorted
for index in range(1, len(array)):
currentValue = array[index]
currentPosition = index
# As long as we haven't reached the beginning and there is an element
# in our sorted array larger than the one we're trying to insert - move
# that element to the right
while currentPosition > 0 and array[currentPosition - 1] > currentValue:
array[currentPosition] = array[currentPosition -1]
currentPosition = currentPosition - 1
# We have either reached the beginning of the array or we have found
# an element of the sorted array that is smaller than the element
# we're trying to insert at index currentPosition - 1.
# Either way - we insert the element at currentPosition
array[currentPosition] = currentValue
簡単な配列を作成し、ソートしてみましょう。
array = [4, 22, 41, 40, 27, 30, 36, 16, 42, 37, 14, 39, 3, 6, 34, 9, 21, 2, 29, 47]
insertion_sort(array)
print("sorted array: " + str(array))
出力
sorted array: [2, 3, 4, 6, 9, 14, 16, 21, 22, 27, 29, 30, 34, 36, 37, 39, 40, 41, 42, 47]
注意：もし while ループの中で条件の順番を逆にしたら、技術的に正しくなかったでしょう。
つまり、array[currentPosition-1] > currentValue があるかどうかを調べてから、 currentPosition > 0 があるかどうかを調べると、技術的に正しくありません。
これは、もし本当に0番目の要素に到達したら、まず array[-1] > currentValue かどうかをチェックすることを意味します。
Pythonでは、これは技術的には間違っていますが、ループが早期に終了したり、継続すべきでないのに継続したりしないので、「良い」のです。
なぜなら、もし0番目の要素に到達していたら、2番目の条件である currentPosition > 0 は最初の条件とは関係なく失敗し、ループが中断してしまうからです。
Pythonでは array[-1] > currentValue は array[len(array) - 2] > currentValue と同じで、インタプリタも文句を言いませんが、これは実際に起こってほしい比較ではありません。
このように条件の順序を逆にすることは悪い考えです。
多くの場合、予期しない結果につながる可能性があり、構文的・意味的なエラーがないため、デバッグが難しくなります。
ほとんどのプログラミング言語では、-1番目の要素にアクセスしようとすると「文句」を言いますが、Pythonは文句を言わないので、そのようなミスを見逃すことは簡単です。
ここから得られるアドバイスは、要素にアクセスするためにインデックスを使用する前に、常にインデックスが有効かどうかをチェックすることです…
カスタムオブジェクトの並べ替え
前に、「より大きい」「より小さい」は好きなように定義できる、つまり整数だけに依存する必要はない、という話をしました。
カスタムオブジェクトを扱うためにアルゴリズムを変更する方法はいくつかあります。
カスタム・クラスの実際の比較演算子を再定義して、上記と同じアルゴリズム・コードを維持することができます。
しかし、その場合、クラスのオブジェクトを別の方法でソートしたい場合は、それらの演算子をオーバーロードする必要があります。
カスタムクラスで Insertion Sort を使用する最も良い方法は、 insertion_sort メソッドに別の引数 (特に比較メソッド) を渡すことである。
これを行う最も便利な方法は、ソートメソッドを呼び出す際にカスタムラムダ関数を使用することである。
この実装では、「小さい」点とは x 座標がより低い点であるとして、点をソートすることにします。
まず、 Point クラスを定義します。
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __str__(self):
return str.format("({},{})", self.x, self.y)
次に、カスタムソートに対応するために insertion_sort メソッドを少し変更します。
def insertion_sort(array, compare_function):
for index in range(1, len(array)):
currentValue = array[index]
currentPosition = index
while currentPosition > 0 and compare_function(array[currentPosition - 1], currentValue):
array[currentPosition] = array[currentPosition - 1]
currentPosition = currentPosition - 1
array[currentPosition] = currentValue
最後に、プログラムをテストします。
A = Point(1,2)
B = Point(4,4)
C = Point(3,1)
D = Point(10,0)
array = [A,B,C,D]
# We sort by the x coordinate, ascending
insertion_sort(array, lambda a, b: a.x > b.x)
for point in array:
print(point)
出力が表示されます。
(1,2)
(3,1)
(4,4)
(10,0)
このアルゴリズムは、適切な比較関数さえ用意すれば、どんな種類の配列に対しても機能する。
挿入ソートの実際
挿入ソートは遅いアルゴリズムのように見えるかもしれませんし、実際、ほとんどの場合、その時間複雑度は O(n2) で実用には遅すぎです。
しかし、これまで述べてきたように、小さな配列やほぼソートされた配列に対しては非常に効率的である。
このため、挿入ソートは大きなデータセットでうまく機能するアルゴリズムと組み合わせて使うのに非常に適している。
例えば、Javaではデュアルピボット・クイックソートを主要なソートアルゴリズムとして使用し、配列（またはクイックソートで作成した部分配列）の要素が7個未満の場合は常に挿入ソートを使用する。
もう1つの効率的な組み合わせは、クイックソートで作成された小さな部分配列をすべて無視し、最終的にほぼソートされた配列を挿入ソートに通すというものだ。
挿入ソートのもう1つの特徴は、シェルソートと呼ばれる非常に人気の高いアルゴリズムである。
シェルソートは、挿入ソートを呼び出して互いに離れた要素のペアをソートし、比較すべき要素間の間隔を徐々に狭めていくことで動作する。
基本的には、まず小さな配列に対して挿入ソートを大量に呼び出し、次に大きな配列に対してほぼソートされた状態で呼び出すことで、可能な限りの利点を活用する。
結論
挿入ソートは非常に単純で、一般的に非効率なアルゴリズムであるが、それにもかかわらず、他の多くの一般的により効率的なアルゴリズムが開発された後でも、それを関連付けるいくつかの特定の利点を持っている。
将来のソフトウェア開発者にソートアルゴリズムの世界を紹介するための素晴らしいアルゴリズムであり続け、それが輝く特定のシナリオのために今でも実際に使用されている。