[ ホーム ] [ TIPS ウィンドウズ系 ] [ TIPS グラフィックス系 ] [ TIPS メルチメディア系 ] [ TIPS 理数系 ] [ TIPS 総覧 ]

上へ
S0001 数式処理
S0002 数式演算
S0003 陰関数のグラフ
S0004 モンテカルロ法
S0005 最小自乗法
S0006 高速冪乗算
S0007 正規乱数
S0008 相関係数
S0101 高速ソート
S0102 高速検索

●解説

　一次元配列のソートは、Array.Sort で簡単に行えるが、複数の条件でのソート(データベースに於ける、 Order By A, C, D など、あるいは下表参照)はコードが必要となる。

　列1、列2、列3の順位でソートした例

●原理

　以下のようにソートする。

• 最初のキーで配列全体をソートする。

• 次のキーで部分(最初のキーでソートされた同じ値の群)ソートする。これをキーの分だけ繰り返す。

●方法

　二次元配列の高速ソート（クイックソート）を用意し、それを利用して部分ソートを行う。ここでは、二次元のObject型配列をソートする例 （列単位で異なる型の実データが可能）を掲げている。ソートする列を自由に指定できるように、ソートキーも二次元配列のIntegerとしている。

• DD(c, r)：cは列の数、rは行の数（データ数）とする。

• kk(1, q)：列0がキー、列1がソート方向、qはキーの数とする。

  • 方向(ソートオーダ)：0が昇順、1が降順である。

●実例

'マルチソートを行う関数

'二次元配列を受けるのは明示的に次元を記述する。（,）
この関数は、指定された配列を直接並べ替えする。A(列, 行)であるとする。

Public Sub MultiQuickSort(ByRef A(,) As Object, ByVal kk(,) As Integer)
    Dim CC As Integer, RC As Integer, Kc As Integer
    Dim i As Integer, j As Integer, k As Integer, ff As Integer, TV As Object
    Dim cL() As Integer, cR() As Integer, cp As Integer
    Dim nL() As Integer, nR() As Integer, np As Integer
    Dim V As Object
    CC = UBound(A, 1) + 1
    RC = UBound(A, 2) + 1
    If RC = 1 Then Exit Sub
    Kc = UBound(kk, 2) + 1
    cp = 1
    ReDim cL(RC) : ReDim cR(RC)
    ReDim nL(RC) : ReDim nR(RC)
    cL(0) = 0 : cR(0) = RC - 1
    For i = 0 To Kc - 1
        np = 0
        For j = 0 To cp - 1
            MQuickSort(A, kk(0, i), kk(1, i), cL(j), cR(j))     'キーに従って部分ソートする
            V = A(kk(0, i), cL(j))
            nL(np) = cL(j) : nR(np) = cL(j)
            For k = cL(j) To cR(j)                             '下位の部分ソート領域を確定
                If A(kk(0, i), k) = V Then
                    nR(np) = k
                Else
                    V = A(kk(0, i), k)
                    np = np + 1
                    nL(np) = k : nR(np) = k
                End If
            Next k
            np = np + 1
        Next j
        cp = np
        cL = nL.Clone : cR = nR.Clone    '配列は参照なので、必ずコピーをする
    Next i
    ReDim cL(0) : ReDim cR(0)
    ReDim nL(0) : ReDim nR(0)
End Sub

'再帰呼び出しのクイックソート基本関数(原理については専門書に依られたい。)

Private Sub MQuickSort(ByRef A(,) As Object, ByVal k As Integer, ByVal D As Integer, ByVal L As Integer, ByVal R As Integer)
    Dim S, T As Object
    Dim CC As Integer
    Dim i As Integer, j As Integer, m As Integer
    CC = UBound(A, 1) + 1
    If L < R Then
        S = A(k, (L + R) \ 2)
        i = L - 1
        j = R + 1
        Do
            Do
                i = i + 1
                If D = 0 Then
                    If A(k, i) >= S Then Exit Do
                Else
                    If A(k, i) <= S Then Exit Do
                End If
            Loop
            Do
                j = j - 1
                If D = 0 Then
                    If A(k, j) <= S Then Exit Do
                Else
                    If A(k, j) >= S Then Exit Do
                End If
            Loop
            If i >= j Then Exit Do
            For m = 0 To CC - 1
                T = A(m, i)
                A(m, i) = A(m, j)
                A(m, j) = T
            Next m
        Loop
        MQuickSort(A, k, D, L, i - 1)
        MQuickSort(A, k, D, j + 1, R)
    End If
End Sub

●改良

　この例だと、値が DBNull の場合には、実行時にエラーとなってしまう。データベースでは、Null は良くあるので都合が悪い。DBNull を考慮する方法もある。ここを参照。