挿入ソート
挿入ソートは、多くの人が手札のトランプを並べる方法です。次のカードを取り、すでに並んでいるカードの中の正しい位置に差し込みます。長いランダムなリストでは遅いものの、短いリストやほぼ整列済みのリストではとても速いため、実際のソートライブラリでも今なお使われています。
考え方
リストの先頭を整列済みに保ちます。最初、整列済みの部分は最初の値だけです。次の値を取り出し、その前の値と比較します。前の値の方が大きければ交換し、1つ前に進んでもう一度比較します。前の値が大きくないか、値が先頭に着いたら止めます。これで整列済みの部分が1つ増えました。最後の値までこれを繰り返します。
例
5, 1, 4, 2, 8で考えます。パス1では1を取り出します。5の方が大きいので交換し、1が先頭に着きます:1, 5, 4, 2, 8。パス2では4を取り出し、5と交換して1で止まります:1, 4, 5, 2, 8。パス3では2を取り出し、5、4と交換して1で止まります:1, 2, 4, 5, 8。パス4では8を取り出しますが、すでに5より大きいので比較1回で済みます。合計で比較7回、交換4回です。同じリストで、バブルソートは比較9回、選択ソートは10回かかります。
交換回数は転倒数と等しい
転倒とは、順序が逆になっている値のペアのことです。順序が逆の隣同士を交換すると転倒がちょうど1つ減り、挿入ソートはそうした隣同士しか交換しません。そのため交換回数は初期リストの転倒数とちょうど等しく、バブルソートと同じです。また各パスには、交換につながらない比較、つまりパスを止める比較が最大1回あります。したがって比較回数は、転倒数に最大n − 1を足したものです。
適応的:ほぼ整列済みのリストで速い
処理量は転倒数におよそnを足したものなので、転倒が少なければ挿入ソートは速くなります。整列済みのリストは比較n − 1回、交換0回です。どの値も本来の位置から数個しか離れていないリストなら、時間はnに近くなります。n²に比例する時間がかかるのは、転倒数がn(n − 1)/2の逆順のリストのように、整列からほど遠いリストだけです。ランダムなリストでは平均で約n²/4回交換します。
使われている場面
挿入ソートは安定で、追加のメモリが不要で、オーバーヘッドもごくわずかです。短いリストなら、理論上はもっと速いアルゴリズムにも勝ちます。PythonやJavaのTimsort、C++で使われるintrosortなど、多くのライブラリのソートは、リストの小さな部分(通常は数十個まで)を挿入ソートに切り替えて処理します。また、値が1つずつ届くデータにも向いています。新しい値が届くたびにすぐ挿入できるからです。
試してみる
アプリを開いて「再生」を押すか、「ステップ」で比較を1回ずつ進めます。挿入中の値には専用の色が付き、比較相手の値は強調表示され、整列済みの部分は緑色です。バブルソートや選択ソートと違って、緑の部分は確定ではありません。後から来た小さい値がまだ入ってくることがあります。まずほぼ整列済みのリストでパスがどれだけ短いかを見て、次に逆順のリストを試してみましょう。
よくある質問
挿入ソートの計算量は?
最悪と平均の場合はO(n²)、最良の場合(すでに整列済みのリスト)はO(n)です。より正確には、nと転倒数の和に比例する時間がかかります。追加のメモリはO(1)だけです。
挿入ソートと選択ソートの違いは?
選択ソートは未整列の部分全体を調べて最小値を探すので、比較は常にn(n − 1)/2回ですが、交換は少なくて済みます。挿入ソートは次の値を順に取り出し、必要な分だけ前に戻すので、比較は少なく(特にほぼ整列済みのリストで)、交換は多くなります。
二分挿入ソートとは?
整列済みの部分で二分探索を使って新しい値の位置を探す方法で、比較は最大n回ではなく約log n回で済みます。ただし場所を空けるために値をずらす必要は残るので、移動回数もO(n²)の最悪の場合も変わりません。
挿入ソートは安定ですか?
はい。値は自分より真に大きい値だけを越えて戻るので、等しい値は元の順序を保ちます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
挿入ソートを試す