情報活用編プラス
第3章「コンピュータとプログラミング」
IP02-12
実践プログラム⑤ 整列アルゴリズム 挿入法
8. その他の並べ替えアルゴリズム ( 8 / 11 )
学習の目的
1. その他の並べ替えアルゴリズム
2. シェルソート
3. クイックソート
これまで、「交換法(バブルソート)」、「選択法」、「挿入法」と3つの並べ替えアルゴリズムを学習してきました。
並べ替えアルゴリズムはこの他にも多くのアルゴリズムが存在します。
この3つ以外にもあるのですか？これ以上あると覚えられないかも⋯
今回学習した3つのアルゴリズムは、並べ替えアルゴリズムとしては基本的なアルゴリズムです。
実際には、数えられないくらい多くの並べ替えアルゴリズムが存在します。
なんで、そんなに多くのアルゴリズムがあるんだろう？
それだけ、並べ替えることが多く、そして時間がかかる処理なので、少しでも効率の良い手順を考えて早く終わらせたいということですね。
ここでは、その他の並べ替えのアルゴリズムとして「シェルソート」と「クイックソート」の2つの紹介をします。
この2つは詳しい手順は覚える必要はありませんが、特徴は覚えておきましょう。
シェルソートとは、挿入法を改良したアルゴリズムです。
挿入法は、ある程度データが順番に並んでいる状態で行った場合、効率が良くなることを学習しましたね。
はい、30%でも事前に並んでいると、時間は半分くらいになりました。
そうそう、データが移動する回数が減るから効率が良いってことだったよな。
シェルソートは、ある程度並べ替えを行ってから最後に挿入法で並べ替えを完成させるアルゴリズムです。
シェルソートは次のように行われます。
次の8個のデータをシェルソートで並べ替えを行う場合の手順を確認しましょう。
gap=4として4つのグループを作成することとします。
グループはそれぞれ色で分かれています。(赤色、黄色、紫色、青色)
4つのグループ内でそれぞれ挿入法で並べ替えを行います。
赤色のグループの並べ替え
黄色のグループの並べ替え
紫色のグループの並べ替え
青色のグループの並べ替え
gapが4のときは次のように並べ替えられます。
ギャップは1になるまで1/2にしていきます。
グループはそれぞれ色で分かれています。(黄色、青色)
2つのグループ内でそれぞれ挿入法で並べ替えを行います。
黄色のグループの並べ替え
青色のグループの並べ替え
gapが2のときは次のように並べ替えられます。
ギャップを1/2にするので、ここで1になります。
gapが1のときは挿入法で並べ替えをします
gapが1のときには、いい感じで並んでいますね。
ほんと、なにかいい感じ並んでるな。
挿入法の欠点は、データが多くなるとデータが遠くまで移動する場合があり、効率が落ちるところです。
シェルソートは、gapで遠くのデータ同士を並べ替えていくので、移動量が少なくなるという利点があります。
クイックソートとは、ある基準を決め、基準より小さいデータと大きいデータにグループ分けをしていきながら並べ替えを行うアルゴリズムです。
クイックって名前がついていると、とても速そうな感じがする！
そうだよね。とっても速く並べ替えができそう。
まさにそのとおりです。クイックソートはとっても速く並べ替えが可能なアルゴリズムです。
それでは簡単にクイックソートのアルゴリズムを確認しましょう。
クイックソートは次のように行われます。
シェルソートと同じデータをクイックソートで並べ替えます。
基準値を決めます。ここでは先頭の 15 を基準値とします。
基準値 15 より小さい値のグループと大きい値のグループに分ける。
このとき、基準の値 15 は位置が確定します。
基準値 8 より小さい値のグループと大きい値のグループに分ける。
このとき、基準の 8 と 小さいグループの 4 の値が確定します。
基準値 12 より小さい値のグループと大きい値のグループに分ける。
このとき、基準の 12 と 13 の値が確定します。
基準値 16 より小さい値のグループと大きい値のグループに分ける。
このとき、基準の 16 の値が確定します。
基準値 18 より小さい値のグループと大きい値のグループに分ける。
このとき、基準の 18 と 20 の値が確定します。
これで、並べ替えが終わりました。
シェルソートもクイックソートも大量のデータを高速に並べ替えるときに向いているアルゴリズムです。
どのくらい並べ替えの時間が違うのか、次のスライドでPythonのプログラムを使って処理時間を比べてみましょう。
