エクセルの使い方
エクセルの使い方を覚えよう




マクロ集目次に戻る


エクセルマクロでアルゴリズムを学ぼう

[an error occurred while processing this directive]

クイックソートの解説

クイックソートの概要

クイックソートとは、下記のようにして並べ替えを行うアルゴリズムです。

  • まず、並べ替えの基本となる値(軸要素などと言われます)を選びます。
  • そして、
    1. 軸要素の左側には軸要素未満のものだけが並ぶようにし、
    2. 軸要素の右側には軸要素以上のものだけが並ぶようにします。

その後、上記の「軸要素の左側」の部分、「軸要素の右側」の部分のそれぞれについて、さらに、上記手順を繰り返していくことで、並べ替えが完了します。

ということで、今回も、左のような適当に並んでいる数字を、右のように並べ替える、というのを例にして考えていきたいと思います(説明の都合上、前回とは、数字の並び順が異なります)。

元の数値
58417 3296
ソート後
12345 6789


クイックソートの具体的な手順

クイックソートとは、下記のようにして並べ替えを行うアルゴリズムです。

スポンサード リンク

  • まず、並べ替えの基本となる値(軸要素などと言われます)を選びます。今回は一番左の値を軸要素として使います。
  • そして、以下の手順を繰り返します(※「左から順に探す」のと「右から順に探す」場所とが交差するまで続けます)。
    1. 左から順に右方向へ軸要素以上となる値を探し、
    2. 右から順に左方向へ軸要素未満となる値(※1)を探し、
    3. その2つの値を入れ替えます。
  • 最後に、※1の結果と軸要素を交換します。

上記の結果、軸要素は真ん中辺りに来ることになり

  1. 軸要素の左側には軸要素未満のものだけが並び、
  2. 軸要素の右側には軸要素以上のものだけが並んでいます。



クイックソートの実際の様子

1巡目:1回目

まず、一番左の値を軸要素とします。そして、軸要素のすぐ右の要素から順に右方向へ軸要素以上となる値を探していきます。

軸要素以上の値を発見するまで、右に進む
584 173 296
その値に目印を付けておく
584 173 296


次に、一番右の要素から左方向へ軸要素以上となる値を探していきます。
軸要素未満の値を発見するまで、左に進む
584 173 296
その値に目印を付けておく
584 173 296


左から走査した値と右から走査した値を入れ替えます
入れ替え前
584 173 296
入れ替え後
524 173 896

1巡目:2回目

右方向へ軸要素以上となる値を探していきます。

軸要素以上の値を発見するまで、右に進む
524 173 896
その値に目印を付けておく
524 173 896


次に、左方向へ軸要素以上となる値を探していきます。
軸要素未満の値を発見するまで、左に進む
524 173 896
その値に目印を付けておく
524 173 896


左から走査した値と右から走査した値を入れ替えます
入れ替え前
524 173 896
入れ替え後
524 137 896

1巡目:3回目

右方向へ軸要素以上となる値を探していきます。

軸要素以上の値を発見するまで、右に進む
524 137 896
その値に目印を付けておく
524 137 896


次に、左方向へ軸要素以上となる値を探していきます。
軸要素未満の値を発見するまで、左に進む
524 137 896
その値に目印を付けておく
524 137 896


左から走査した値と右から走査した値が交差しているので、右から走査した値(赤色)と軸要素(黄色)を交換します。
入れ替え前
524 137 896
入れ替え後
324 157 896

2巡目:1回目

ここで、軸要素(5)を境目として、左側には軸要素よりも小さい数値、右側には軸要素よりも大きい数値が並んでいることがわかると思います。そこで、さらに、軸要素の左側の4つの数字、右側の4つの数字について、クイックソートのアルゴリズムを繰り返していくことで、ソートが完了します。

クイックソートの特徴

スポンサード リンク

クイックソートの特徴的なところとしては、下記のような点があります。ただ、実用的なソートアルゴリズムとしては、非常にバランスのとれたアルゴリズムであることに間違いはありません。



  • 元々の値が、ランダムに並んでいる場合には、計算速度は非常に早く、計算時に要するメモリ空間もほとんどない。
  • 元々の値が、すでにソートされていたり、逆順にソートされており、軸要素として選んだ値が並べ替え対象の要素の中で最大又は最小となる場合には、計算速度は非常に遅い。



クイックソートのエクセルマクロ

クイックソートマクロのダウンロード

クイックソートのダウンロードはこちらからどうぞ




クイックソートマクロの使い方

  • ダウンロードしたエクセルファイルを開きます。
  • マクロを実行してもよいかどうかを聞くウィンドウが表示されますので、「はい」をえらびます。
  • 「Ctrl」と「Shift」を押したままで「Q」のキーを押します。

これで、プログラムの実行が開始されます。



免責事項

このプログラムを実行したことによる一切の損害について責任は負いかねます。ご自身の責任でご利用ください。

マクロ集目次に戻る


「経理事務のためのエクセル基礎講座(初級編)」(動画マニュアル 総収録時間162分)を無料プレゼント中です!

このマニュアルで解説していることを一通り学べば、経理事務を行う上で最低限必要となる知識が得られます。

ご登録者の方には、合わせて、公認会計士が実体験を通して身に付けたエクセルを使う技をメールにてお伝えしていきます!

↓ 登録はこちら ↓
名字
名前
メールアドレス


 





姉妹サイト:
情報処理技術者試験対策   逆ポーランド記法  

[an error occurred while processing this directive]