目次
はじめに
基本情報技術者試験や応用情報技術者試験でよく出題される整列アルゴリズムの問題。
基本的な整列アルゴリズムには「バブルソート」「選択ソート」「挿入ソート」があり、より高速な整列アルゴリズムには「シェルソート」「クイックソート」「ヒープソート」「マージソート」があります。
スポンサーリンク
本記事では、適当な基準値を定めて並び替えを繰り返していく「クイックソート」について図解で分かりやすく解説しています。
クイックソートとは
クイックソートとは、適当な基準値を定めて「基準値より小さい値」のグループと「基準値より大きい値」のグループに分ける作業を繰り返して整列していく手法です。
クイックソートの流れ
- 適当な基準値を定める
- 「基準値より小さい値」のグループと「基準値より大きい値」のグループに分ける
- グループ内で再度、適当な基準値を定める
- 「基準値より小さい値」のグループと「基準値より大きい値」のグループに分ける
- 処理1～4を繰り返して整列していく
暗記ポイント
クイックソートは適当な基準値を選び、それより小さな値のグループと大きな値のグループにデータを分割する。この作業を繰り返して整列していく整列アルゴリズム
【手順1】基準値を決める
まず基準値を決めます。データの中央値が望ましいのでここでは"4"を基準値とします。
【手順2】基準値より「小さいグループ」と「大きいグループ」に分ける
次に基準値より「小さいグループ」と「大きいグループ」に振り分けていきます。
小さいグループ：3、1、2
大きいグループ：5、7、8、6
※基準値「4」の位置は確定
【手順3】「小さいグループ」の基準値を決める
「小さいグループ」の中で基準値を決めます。
ここでは"2"を基準値とします。
【手順4】「小さいグループ」の基準値より「小さいグループ」と「大きいグループ」に分ける
「小さいグループ」内の基準値より「小さいグループ」を更に振り分けていきます。
「小さいグループ」内の基準値より小さい：1
「小さいグループ」内の基準値より大きい：3
※「1」「2」「3」の位置は確定
スポンサーリンク
【手順5】「大きいグループ」の基準値を決める
「大きいグループ」の中で基準値を決めます。
ここでは"6"を基準値とします。
【手順6】「大きいグループ」内の基準値より「小さいグループ」と「大きいグループ」に分ける
「大きいグループ」内の基準値より「大きいグループ」を更に振り分けていきます。
「大きいグループ」内の基準値より小さい：5
「大きいグループ」内の基準値より大きい：7、8
※「5」「6」の位置は確定、最後に7もしくは8を基準値として「7」,「8」の位置も確定させる
[基本整列アルゴリズム]
[高速整列アルゴリズム]