情報活用編プラス
第3章「コンピュータとプログラミング」
IP02-12
実践プログラム⑤ 整列アルゴリズム 挿入法
4. 挿入法の並べ替えの手順を確認しよう ( 4 / 11 )
学習の目的
・ 挿入法の手順
挿入法での並べ替えをコンピュータでする場合は、1つの配列で行うことが多いです。データが多い場合、並べ替え用の配列を作り並び順だけが異なる同じデータの配列を2つ持つことは、メモリを余分に使用することになり無駄が多いためです。
それではコンピュータがどのようにして1つの配列で挿入法を実行していくか確認しましょう。
並べ替える前のデータは次のとおりです。
このデータを昇順に並べ替えを行います。
挿入法は、0番目のデータが入っている状態で、1番目以降のデータを一つずつ挿入しながら並べ替えを行います。
0番目のデータはすでに挿入済みという想定の状態から処理を始めます。
最初のデータは、整列済みデータです。
最初の1件目はデータが1つしかないという状態なので自然と昇順に並んでいることにもなります。
添字1のデータ12を次の手順で挿入します。
手順通りに確認しましょう。
データが挿入され、2件のデータが整列済みとなっていま。
1番目のデータ12が正しい位置に挿入されましたね。
続いて2番目のデータ 18 を挿入します。
添字2のデータは移動はありませんが、挿入法では、挿入位置が決まったら、移動がない場合でも、プログラムの中では「比較して、同じ場所に代入する」という処理が行われます。
これも「挿入」として扱います。
ここは、挿入法での重要なポイントです。
挿入位置が決まるまで、確定済みデータの右端から順番にデータを右側へ移動させていきます。
このように、挿入法はデータを挿入しながら並べ替えを行います。
データを入れていくと並べ替えが終わってるって、なんかすごい！
そうですね。入れながら並べ替えるため、交換法や選択法に比べ比較回数が少なくなっていることが特徴です。
挿入法をもっと確認したい場合は、「アルゴリズム学習ツール」を使ってみましょう。
次のリンクをクリックして体験してみましょう。
