037-アルゴリズム-挿入ソート【新人エンジニアが最初に覚えたい100のJava文法】シミュレーターあり
山崎講師ユーチューブ動画
挿入ソートについて解説します。
ソースコード
public class ArgoSortInsert {
public static void main(String[] args) {
int[] data = { 30, 60, 70, 90, 20 };
sort(data);
for(int element : data){
System.out.print(element + " ");
}
}
public static void sort(int[] data) {
for(int i = 1; i < data.length; i++){
int tmp = data[i];
int j = i;
while(j > 0 && tmp < data[j - 1]){
data[j] = data[j - 1];
j--;
}
data[j] = tmp;
}
}
}
解説
挿入ソートについて解説します。
プログラムを組み立てるときには、プログラムの解法が必要です。
プログラムの解法をアルゴリズムといいます。
代表的なアルゴリズムを覚えておくと、将来いろいろなプログラムを組むときのヒントになります。
ここでは、挿入ソートを紹介します。
ソートは並び替えです。
サンプルコードでは、配列dataを並び替えるため、sortメソッドを呼び出し、for文で並び替えた後の要素を出力しています。
なお、for文では拡張for文が利用されているので、配列dataの要素を１つ取り出し、変数elementに入れることで繰り返し出力しています。
挿入法は、ソートしていない部分とソートしている部分に分けるところから始まります。
ソートしていない部分から要素を一つ取り出し、ソートしている部分の中で適切な場所に挿入するアルゴリズムです。
１回目の繰り返しでは、最初のfor文で要素の1番目を取り出し、変数tmpに代入します。
変数tmpは60になります。
変数iから変数jに代入し、次のwhile文で、挿入する部分を探します。
1回目の繰り返しでは、tmp<data[1-1]になるので、0番目の要素と比較します。
しかしTmpのほうが大きいので、whileの処理には入りません。
また変数jの値は変わりません。よって、変数tmpの値をdata[1]に戻して、終わります。
続けていくと、70を取り出したとき、90を取り出したときには、変化しません。
最後の繰り返しで、4番目を取り出し、変数tmpに代入します。変数tmpは20になります。
変数jには4が入ります。While文は、tmp<data[4-1]、つまり20<90となり、継続条件を満たします。
すると、data[4]=data[4-1]となり、20が入っていたところに、90が入ります。Jの値が1減ります。
次のtmp<data[3-1]でも、20<70となり、継続条件を満たします。
すると、data[3]=data[3-1]となり、90が入っていたところに、70が入ります。
このように配列の要素をずらしていくと、ｊが1になったとき、data[1]=data[1-1]となり、
60が入っていたところに30が入り、jが0になって、whileを抜けます。
最後にdata[0]に変数tmpの20が挿入されて、ソートが終了します。
いかがでしょうか？
頭の中だけで考えずにぜひ書き出して考えてみてください。
以上、挿入ソートについて解説しました。
このサンプルコードをJavaタッチタイプゲームとして遊ぶことができます。
投稿者プロフィール
- 代表取締役
-
セイ・コンサルティング・グループ株式会社代表取締役。
岐阜県出身。
2000年創業、2004年会社設立。
IT企業向け人材育成研修歴業界歴20年以上。
すべての無駄を省いた費用対効果の高い「筋肉質」な研修を提供します！
この記事に間違い等ありましたらぜひお知らせください。
最新の投稿
新入社員2024年11月23日「ゲシュタルト崩壊」とシステム開発- 新入社員2024年11月23日データベースでテーブル名やフィールド名にスペースを使うことは、一般的には推奨されていません
- 新入社員2024年11月23日「データにはなぜ型が必要なのか？」を2進数の観点から解説
- 新入社員2024年11月23日ディスプレイの解像度の意味と変更方法
