Pythonとか)挿入ソート挿入ソートとは挿入ソートとは、ソート済の部分に新たなデータを適正な位置に挿入していくことで、ソートを行います。概ねソート済のデータに対しては、交換(挿入)回数が少なく済むため高速に動作します。この特性を活かすように改良されたアルゴリズムがシェルソートです。ソート対象のデータ数が少ない場合も高速になります。これはクイックソートなどの高速なソートはオーバーヘッドが大きくなるためです。大体50件程度のデータ以下なら、クイックソートより平均して速くなりそうです。バブルソートと同じで低速なのですが、前述の通り、一定の条件下では高速に動作する可能性があります。挿入ソートのシミュレーション背景色が黄色のタイミングで比較が実行されています。緑色はソート済(確定ではない)の部分です。ここにデータを挿入します。ソート済のデータは水色になります。最終要素まで走査しなければ最小値(最大値)は確定しません。よって上位3件だけ取得する用途でも全データをソートする必要があります。この点は選択ソートなどと違います。アルゴリズムの解説データ(array)の先頭要素をソート済のデータとして考えます。までループし、i番目の要素を挿入することを考えます。※この際、交換処理を繰り返しながら挿入すると遅くなるので、i番目の要素を一時変数に退避し、配列の値を上書きしてずらすようにします。退避していたi番目の値を入れます。0~i番目の値ソート済となっています。2.のループが終われば末尾の要素までがソート済のデータとして得られます。