【Java】誰でもわかる!挿入ソート!

 

プログラミングの勉強のし始めで、ソートを勉強している人も多いかと思います。

そこで今回は、挿入ソートについて誰でもわかるように解説をしてみます!

まずはソースコードから。

【Java】挿入ソート

int array[] = {3,5,6,2,9,1} ;
void insertSort(){
    int tmp,j ;
    for(int i = 1 ; i < array.length ; i++){
	tmp = array[i] ;
	j = i-1 ;
	
	while(  array[j] > tmp && j >= 0 ){
	    array[j+1] = array[j] ;
	    j-- ;
	}
	array[j+1] = tmp ;
    }
}

 

これで理解できる天才君はブラウザバック!!

当時、僕は「何やってんの?わけわからんわ。」と思い、丸暗記してテストに挑んだ記憶があります…バカは困りますね…

ちょっと解説をしますと。

『整列済みのもの』と『未整列』の2種類で考えます。

初めのarray[0]の3は、もうすでに整列済みなので、そのまま。

次にarray[1]の5は、未整列の値になるので、整列しているの数字に対してどこに入るかなーと探します。

array[0]とarray[1]を比べるわけですよ。

んで、array[0] < array[1]つまり、5 < 6 でtrueだー!となるので、そのまま。1番目の値も整列済みとなります。

次も同じように、未整列のarray[2]の6を取り出してもtrueだー!となるのでそのまま。

次は、未整列のarray[3]番目の2を取り出します。この2は整列済みのものと比べるとどこかに挿入しなきゃいけませんよね?

そこで整列済みの右から順に比べていって入れるところを探して、挿入!といった流れをひたすら繰り返します。

 

実際に値を代入して調べて見ましょう。

 

実際に挿入ソートをしてみる。

ここからは画像を使った方がわかりやすいかな?と思ったので画像になります。

 

これを繰り返していくといずれソートされます。

実際に手を動かしてやってみるとわかると思いますので、この先は自分で手を動かしてみることをオススメします。

 

挿入ソートの計算時間

計算時間はO(n^2)となります。

バブルソートも同じように計算時間はO(n^2)となりますが、挿入ソートのほうが高速。

感の鋭い人はわかるかもしれませんが、

バブルソートは元の数列に依存せずにソートしますが、挿入ソートの場合、もうすでにほとんど整列しれいれば(バブルソートを比べると)早くなります。

 

以上!

 

1 Comment

Unknown

そのプログラム、配列要素が-1になる可能性があるので
public static int[] insertSort2(int[] date) {
int root=0;
for (int i=1;i<date.length;i++) {
int tmp = date[i];
if (tmp 0)&&(tmp<date[j-1])); j–) {
date[j] = date[j-1];
root = j;
}
date[root-1] =tmp;
}
}
return date;

こっちのほうがわかりやすいと思う

返信する

コメントを残す

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください