「目次」
1. 今日のプログラミング
前回は順番を前後してしまいシェルソートからしてしまったので、
今回は、シェルソートの元になっているインサートソートをやっていきたいと思います。
環境
VisualStadio 2022
C#
2. インサートソート
インサートソートとは、整列してある配列に追加要素を適切な場所に挿入する、ソートアルゴリズムの一つです。
このソートアルゴリズムの強いところは、
- アルゴリズムが単純で実装が簡単
- 短い（小さい）配列に対しては高速
- 処理速度が安定したソートアルゴリズム
逆に弱いところは、
-
整列された小さい配列に「速い」ので、ぐちゃぐちゃで大きい配列には
不向き。
-
逆順のリストを対象にした場合、めちゃくちゃ遅くなる。
-
処理の時間が並び方によって左右される。
という感じの、使える場所が限られそうなソートアルゴリズムですね。。。
—内部の動き—
※比較対象 赤
ソート済み 緑
配列[5,3,2,4,1]で考えてみましょう。
一回目
まずは5と3を比べます。
5，3，2，4，1
5 ＞ 3 Insert
3、5、2、4、1
二回目
次に、2と5と3を比べます。
3、5、2、4、1
3 ＞ 2 Insert
5 ＞ 2 Insert
2、3、5、4、1
三回目
次に4と5と3と2を比べます。
2、3、5、4、1
2 ＜ 4 NoInsert
3 ＜ 4 NoInsert
5 ＞ 4 Insert
2、3、4、5、1
四回目
最後に1とすべてを比べます。
2、3、5、4、1
2 ＞ 1 Insert
3 ＞ 1 Insert
4 ＞ 1 Insert
5 ＞ 1 Insert
1、2、3、4、5
ソート完了です。
やってみましょう。
namespace InsertSort
{
internal class Program
{
static void Main(string[] args)
{
int[] number = {9,0,6,8,7,3,2,5,1,4};
InsertSort(number);
for(var i = 0; i < number.Length; i++)
{
Console.WriteLine(number[i]);
}
while (true) ;
}
public static void InsertSort(int[] array)
{
for(var i = 0; i < array.Length; i++)
{
var insertNumber = array[i];
var insertPosition = i;
for(var j = insertPosition - 1; j >= 0; j--)
{
//右にシフトする
if(insertNumber < array[j])
{
array[j + 1] = array[j];
insertPosition--;
}
}
//新しい要素を挿入
array[insertPosition] = insertNumber;
}
}
}
}
実行結果
0
1
2
3
4
5
6
7
8
9
これはイメージがつきやすいのではないでしょうか？
自分は紙に書いて要点を整理していたら簡単にかけてしまいました。
ここが理解できれば、シェルソートもできるはずです。
自分でいろいろなケースを想定して、自分なりのコードを書いてみましょう！
まとめ
前後しましたが書いてる側としては、「あ、ここシェルソートで使った」
という点が多々ありました。
そういうとこに気付けるようになってる自分でも驚きました。
微々たる成長を感じられてモチベーションが上がりましたｗ
参考にしたサイト☟
https://ja.wikipedia.org/wiki/挿入ソート
https://www.codereading.com/algo_and_ds/algo/insertion_sort.html