情報活用編プラス
第3章「コンピュータとプログラミング」
IP02-12
実践プログラム⑤ 整列アルゴリズム 挿入法
3. 挿入法とは ( 3 / 11 )
学習の目的
1. 挿入法とは
2. 挿入法の手順
挿入法とは、交換法(バブルソート)や選択法と並ぶ代表的な整列アルゴリズムの一つです。
挿入法は、交換法や選択法より効率がいい整列アルゴリズムです。
速く並べ替えられるってことですね。どのくらい速いんだろう？
挿入法は、データがある程度並んでいるときはとても速く動きますが、並び順がばらばらのとき（最悪の場合）は、交換法（バブルソート）と同じくらいの回数になります。
最悪の時で同じくらいってすごい！どうやっているんだろう？
挿入法は名前の通り「データを挿入しながら並べ替える」方法です。
並べ替えのイメージは次のとおりです。
挿入法とはどのように並べ替えを行うか確認しましょう。
次の5枚のトランプを挿入法で昇順に並べ替える例を見ていきましょう。
挿入法はデータを挿入するときに並べ替えを行う方式です。今回はわかりやすく、整列用領域に並べ替える方法を説明します。
トランプを数字の小さい順に下にある「整列用領域」に並べるってことですね。
なるほど。でもなんでトランプが裏返っているんだろう。
挿入法では、整列用領域（すでに並んでいる部分）と、次に入れる1枚のトランプだけを見れば並べ替えができます。
では、早速並べ替えをやっていきましょう。
挿入法は整列用領域に入れるときには並べ替え済みになっているようにデータを挿入します。
1番目のデータは他にデータがないので一番小さい値なので、無条件に先頭に入ります。
2番目のトランプをめくります。
めくったトランプが整列用領域のどこに入るか調べます。
クローバーの2が入る場所はどこかわかりますか？
はい！5の前ですよね。
そうですね。5の前には空いている場所がないので、次のように5を横に移動して2が入る場所を作ります。
なるほど、場所を作ってから入れるのですね。
2を入れる時に、並べ替えができているように位置を調整しながら挿入していきます。
3枚目のトランプは8です。8は5より大きいので3番目に入れます。
4枚目のトランプは3です。3は2と5の間なので、5と8を右にずらし空いたところに3を入れます。
5枚目のトランプは6です。6は5と8の間なので、8を右にずらし空いたところに6を入れます。
このように、データを挿入する時に位置を探してからデータを入れるので、入れたときには並べ替えが終わっています。
なるほど、入れる時に順番を考えて入れるってところがこれまでと違ってますね。
確かに、毎回全部比較していた交換法や選択法と比べても効率がいいんじゃないかと思う。
それでは、コンピュータを使って挿入法を行うにはどうしたらよいか考えていきましょう。
