HeapSort Function & Procedure For VBA（ヒープソートアルゴリズム）

ヒープソート(Heap Sort)のVBAコードを紹介します。クイックソート(Quick Sort) をVBAで使うとエラーが発生するので、長い配列の並び替えをする場合にこのコードがあるととても重宝すると思います。N² の原始的なソート方法とは比較にならないほど早いです。

Quick Sort Algorithm (クイックソート)

ソートのアルゴリズムについて： ソートのアルゴリズムの計算量は、分かりやすいように大きく２つに分類すると、N²とN*Log N に分けられます。アルゴリズムを構築する場合、この "N" はとても大きな数値だと仮定しなければいけません。下のテーブルのように、計算量がN² の 1/100 となったとしてもアルゴリズム上の理論値は N²です。

The VBA code of heap sort is end of this article. I think that it is found useful very much if there is this code when sorting long array, because an error will occur if quick sort is used by VBA. It is so fast that it cannot be compared with the primitive method.

下のコードはに、３つの N² のアルゴリズムのソートです。１つ目のソートは、順番に小さい数値を見つけて挿入していくソートです。このソートは、N² * 1/2 の計算量です。２つ目は、最初と最後を比較していくソートで、３つ目は一番小さい数値と大きな数値を見つけて挿入するソートです。このソートは、N² * 1/4 の計算量です。4つ目は、一番小さい数値と大きな数値を２つ見つけて挿入するソートです。計算量は、N² * 1/6 になります。膨大な量のデータをこういった原始的なアルゴリズムで並び替えようとすると大変なことになります。

These are 4 samples of primitive method which takes quantity of calculation N².

下のリンクに続きます。

初めてヒープソートのアルゴリズムを見るのであれば、理解するのに少し時間がかかるかもしれません。まずは、下のテーブルとイメージのリンクを見てください。親と２つの子の位置関係が分かれば理解し易くなります。最初の DownHeap の呼び出しで、親は必ず２つの子よりも大きくなるように並び替えられます。

次にループで、最初の配列に一番大きな数値が入ってますので、配列の（最後－0)と最初を、次にDownHeap してから、配列の（最後－1)と最初を、次にDownHeap してから、配列の（最後－2)と最初を（順番に最後＝２番目の位置になるまで）入れ替えます。

If you look at the algorithm of a heap sort for the first time, understanding may take time for a while. First of all, please look at a table and the link of an image. It may become easy to understand if you understand the spatial relationship of parents and two children as shown in table.

After calling of DownHeap, array will be rearranged so that parent will become larger than two children.

Heap Sort Image

Sub と　Function を使って Heap Sort を使用する方法です。Sub Program を呼ぶと配列が並び替えられます。HeapSort_Func を使うと "Temp" に並び替えられた配列が別に生成されます。用途に応じて使い変えます。

These are Sub & Function of Heap Sort. If Sub Program is called, then array will be sorted. If HeapSort_Func is used, the array will be sorted into "Temp" which will be generated independently. it can be changed according to a use.

Dim Temp As Variant
   Temp = HeapSort_Func(Ar) ''-------- For using Function 

   Call HeapSort_Sub(Ar)　　''-------- Call Sub program

the code below is the method of carrying out Heap Sort. Arrangement will be rearranged if Sub Program is called. If Heap Sort Function is used, the array is rearranged into "Temp" will be generated independently.

NOTE:ヒープソートのコードを訂正しました。 こちらに訂正したHeapSortのコードを紹介しています。

NOTE:The code of HeapSort corrected at this page

もし配列の長さが大きくなった場合、以下のコードは消してください。

If size of array is large, then it is more efficient to erase the codes below.

  If Ar(0) < Ar(1) And i = 1 Then Exit For

   If i <= 1 Then Exit For