情報処理技術者試験対策 > アルゴリズム > クイックソート

クイックソートについての説明

クイックソートは、下記のような手順を繰り返して並べ替えを行うソートアルゴリズムをいいます。

  1. まず、並べ替えの基本となる値(軸要素などと言われます)を選びます。今回は一番左の値を軸要素として使います。
  2. そして、以下の手順を繰り返し、左から順に探すのと右から順に探すのとが交差するまで続けます。
    • 左から順に軸要素以上となる値を探し、
    • 右から順に軸要素未満となる値(※1)を探し、
    • その2つの値を入れ替えます。
  3. 最後に、※1の結果と軸要素を交換します。
  4. 上記の結果、軸要素は真ん中に来ることになり、
    1. 軸要素の左側には軸要素未満のものだけが並び、
    2. 軸要素の右側には軸要素以上のものだけが並んでいます。
    そこで、上記の1、2のそれぞれの部分について、さらに、上記手順を 繰り返していきます。

クイックソートの具体例

今回は、下のような適当に並んでいる数字を、右のように並べ替える、というのを例にして考えていきたいと思います。

5 8 4 1 7 3 2 9 6 →  1 2 3 4 5 6 7 8 9

クイックソートのアルゴリズム具体例

1巡目

軸要素を一番左の値「5」として実行していきます。軸要素を除いて、左から検索して軸要素以上となる「8」と右から検索して軸要素未満となる「2」を交換します。

クイックソート1巡目1つ目

今入れ替わった値の内側をさらに検索していきます。左側から右に向けて検索して軸要素以上となる「7」と、右側から左に向けて検索して軸要素未満となる「3」を交換します。

クイックソート1巡目2つ目

さらに内側に向けて検索していくと、検索する場所が交差してしまいます。そこで、その交差した点の左側の「3」と軸要素の「5」を交換します。

クイックソート1巡目3つ目

2巡目左側

軸要素を一番左の値「3」として実行していきます。左から検索して軸要素以上となる「4」と右から検索して軸要素未満となる「1」を交換します。

クイックソート2巡目1つ目

次に検索していくと、検索する場所が交差してしまうので(左からは4まで来て、右からは1まで来る)、あとは交差した点の左側の「1」と軸要素「3」を交換します。

クイックソート2巡目2つ目

次に、3の左側の2個をソートしていきます(今回の場合はすでに並べ替えられていますが)。また、3の右側も本来はソートする必要があるのですが、残りの数字が1個だけなので、こちらもソート完了です。

結果的に、左の4つは「1 2 3 4」という順番に並び替えられることになります。


2巡目右側

軸要素を一番左の値「7」として実行していきます。左から検索して軸要素以上となる「8」と右から検索して軸要素未満となる「7」を交換します。

クイックソート2巡目1つ目

次に検索していくと、検索する場所が交差してしまうので(左からは9まで来て、右からは6まで来る)、あとは交差した点の左側の「6」と軸要素「7」を交換します。

クイックソート2巡目2つ目

同じように7の左側の「6」を並べ替えます(残りの数字が1個だけなので、並べ替えはすでに完了していますね)。また、7の右側の「9 8」も同様に並べ替えていきます。

結果的に、右の4つは「6 7 8 9」という順番に並び替えられることになります。

これで、並び替えが完了します。

カテゴリ一覧
アルゴリズム
アルゴリズムとは  ソートアルゴリズム  バブルソート  インサーションソート  クイックソート  マージソート  ソートアルゴリズムを体感する