Search先日書いたクイックソートの記事で少し勘違いしてた部分がありましたので書き換えました。今回は、Procedure と Function の両方のコードを紹介します。ExcelVBAのレベルでは、今のところこういったソートを個人レベルで利用することはあまり必要ではありませんが、多くの人が使うアドインなどに組み込む場合は必要です。クイックソートの他にヒープソート(Heap Sort)と呼ばれる（これも計算量：N*Log N）で安定したソート方法がありますので次の記事で紹介します。
QuickSort のアルゴリズムを用いたVBA 用のコードを紹介します。このアルゴリズムは配列に適しています。クイックソートはある条件下において、効率が悪くなることがあります。このアルゴリズムは、比較するためのPivotを配列の中心の値にしてますが、本来のPivot の位置は配列の先頭の値です。この場合だと、降順を昇順に、または昇順を降順にソートする場合に処理量がN²となってしまいます。Pivotの位置を変えても、一定の条件下では効率が悪くなることがあります。イントロソートと呼ばれるソート方法がありますが、これはクイックソートの効率が悪くなる条件の場合、ヒープソートに切り替えるものです。
しかし、平均的に、N*Log N の処理量を実現してますので、とても優秀なアルゴリズムです。しかしながら、エクセルVBA のレベルでは、配列が大きくなったとき、「スタック領域・・・」とエラーが出て、あまり使えそうにありません。長い配列を使う場合はヒープソートを使うといいと思います。本来は、本当に処理速度を追求するのであれば、配列なんて便利なものは使えません。便利なものは必ず何かを犠牲にします。
クイックソートが作られた時代に配列などはなく、データ構造はレコードをポインターで繋いだ構造でした。ポインターを使うことでとても自由なプログラミングが可能になりますが、一度ポインターが切れるとデータは２度と捕まえることが出来ません。その環境で書かれたプログラムは、アルゴリズムが完成してないと、厄介なプログラムになってしまいます。 ２０年前に、ポインターをネットワーク状に張り巡らせたソートプログラムを作りました。少しだけメモリを使いますが、安定したプログラムでした。機会があったら紹介したいと思います。
I rewrote this article, since there was a portion which misunderstood with the article of quick sort written the other day. Although it is not so much required on the level of ExcelVBA to use such sorting on an individual level for the moment. It is called the "Heap Sort" other than quick sort which is the stable sorting method, it introduces with the following article.
This is code of QuickSort Function & Procedure which is written in VBA. This algorithm is suitable for sorting array. Since quick sort has realized the amount of processings of N*Log N, it is a very excellent algorithm on the average, also sometimes its efficiency may worsen under a certain condition. Although this algorithm makes Pivot for comparing the value of the center of arrangement, the position of original Pivot is a value of the head of arrangement. The amount of processings will be N² if quicksort sort an ascending order to descending order. Even if it changes the position of Pivot, efficiency may worsen under certain conditions. Although there is the sorting method called "intro sort". this method will change to a heap sort, when the efficiency of quick sort is the worsening conditions. if processing speed is pursued truly, a convenient thing cannot be used. convenience sometimes sacrifice something.
I was writing Pascal. It's very free programming is attained by using a pointer. The program written in the environment will turn into a troublesome program, if the algorithm is not completed. 20 years ago, I have made the sorting program which spread the pointers around in the shape of a network. it was the more stabilized program than quick sort. I want to introduce, when there is an opportunity.
Sub と Function を使って QuickSort をする方法です。Sub Program を呼ぶと配列が並び替えられます。QuickSort_Func を使うとTempに並び替えられた配列が別に生成されます。用途に応じて使い変えます。あまり長い配列だと「スタック領域」のエラーが出ます。
このクイックソートは、少しアレンジを加えています。ソートする配列が２つ、または３つの場合は処理量は決まっていますので、無駄な計算を省くためにクイックソートで処理する前にチェックして処理しています。
Dim Temp As Variant Temp = QuickSort_Func(Ar) ''-------- Use Function ByRef Call QuickSort_Sub(Ar) ''-------- Call Sub program
the code below is the method of carrying out QuickSort. Arrangement will be rearranged if Sub Program is called. If QuickSort Function is used, the arrangement rearranged into "Temp" will be generated independently.