クイックソートとは

IT用語

クイックソートとは | 分かりやすく図解で解説

はじめに

情報処理試験問題でよく登場する整列アルゴリズムの問題。

基本的な整列アルゴリズムには「バブルソート」「選択ソート」「挿入ソート」があります。そしてより高速な整列アルゴリズムには「シェルソート」「クイックソート」「ヒープソート」「マージソート」などがあります。

スポンサーリンク

本記事では、中間的な基準値を定めて並び替えを繰り返していく「クイックソート」について図解を利用してわかりやすく解説しています。

クイックソートとは

クイックソートとは、中間的な基準値を定めて、「基準値より小さい値」のグループと「基準値より大きい値」のグループに分け、その後それぞれのグループ内で再度、中間的な基準値を定めてでソートを繰り返していく手法。

  1. 中間的な基準値を定める
  2. 「基準値より小さい値」のグループと「基準値より大きい値」のグループに分ける
  3. グループ内で再度、基準値を定める
  4. 「基準値より小さい値」のグループと「基準値より大きい値」のグループに分ける
  5. この流れを繰り返して整列を行う方法です。

 

それでは具体的に図解でシェルソートの流れを説明していきます。

 

暗記ポイント:クイックソートは基準値を決めて基準値より小さい・大きいの振り分ける処理を繰り返していく整列アルゴリズム

【手順1】中間的な基準値を決める

まず中間的な基準値を決めていきます。データの総数の中央値が望ましい値です。

ここでは"4"を基準値とします。

クイックソート手順1

【手順2】基準値より「小さいグループ」と「大きいグループ」に分ける

次に基準値より「小さいグループ」と「大きいグループ」に振り分けていきます。

小さいグループ:3、1、2

大きいグループ:5、7、8、6

クイックソート手順2

【手順3】「小さいグループ」の中間的な基準値を決める

「小さいグループ」の中で中間的な基準値を決めていきます。

ここでは"2"を基準値とします。

クイックソート手順3

【手順4】「小さいグループ」内の基準値より「小さいグループ」を更に振り分ける

「小さいグループ」内の基準値より「小さいグループ」を更に振り分けていきます。

「小さいグループ」内の基準値より小さい:1

「小さいグループ」内の基準値より大きい:3

クイックソート手順4

スポンサーリンク

【手順5】「大きいグループ」の中間的な基準値を決める

「大きいグループ」の中で中間的な基準値を決めていきます。

ここでは"6"を基準値とします。

クイックソート手順5

【手順6】「大きいグループ」内の基準値より「大きいグループ」を更に振り分ける

「大きいグループ」内の基準値より「大きいグループ」を更に振り分けていきます。

「大きいグループ」内の基準値より小さい:5

「大きいグループ」内の基準値より大きい:7、8

クイックソート手順7

 

 

[基本整列アルゴリズム]

[高速整列アルゴリズム]

Copyright© ITを分かりやすく解説 , 2020 All Rights Reserved Powered by AFFINGER5.