Sub 縦方向ソート()
Dim i As Integer
Dim waku As Range
For i = 0 To columnmax - 1
Set waku = Range(Cells(1, i + 1), Cells(rowmax, i + 1))
waku.Sort key1:=Cells(1, i + 1), order1:=xlAscending, Orientation:=xlSortColumns
Next
End Sub
Sub 横方向ソート()
Dim i As Integer
Dim waku As Range
For i = 0 To rowmax - 1
Set waku = Range(Cells(i + 1, 1), Cells(i + 1, columnmax))
If i Mod 2 = 0 Then
waku.Sort key1:=Cells(i + 1, 1), order1:=xlAscending, Orientation:=xlSortRows
Else
waku.Sort key1:=Cells(i + 1, 1), order1:=xlDescending, Orientation:=xlSortRows
End If
Next
End Sub
上はエクセルのマクロの抜粋です。
ごめんなさい、思いっきり手を抜きました。
ソートを作るんだから、既存のソート関数を使ってはいけないのですが、
思いっきりSortという文字が見えます。
今回は、縦ソート、横ソートに何を使うか考えてみます。
普通に考えればシェアソートを再帰する方法です。
ですが、シェアソートは順列（すでにソート済みの状態）であっても
交換が発生してしまうため、順列の検出が出来ません。
なお、縦ソート、横ソート共に交換が発生しなかったら終了という条件ですが、
実際には2回目以降なら縦ソートか横ソートのどちらかで順列を検出すればOKです。
なぜなら、縦ソート後は縦ソートをしても交換が発生しない状態だからです。
順列の検出といえばバブルソートです。
これを縦ソートに使ってやれば順列の検出が出来るし、
縦ソートはそれほど要素が変わらないため、
バブルソートでも十分速度が出ると考えられます。
ただし、横ソートにバブルソートを使った場合、
最大要素や最小要素が先頭や末尾に来ることが多いため
バブルソートの最悪パターンに陥りやすいため、不向きと言えるでしょう。
こちらはシェアソートを再帰させるべきです。
なお、最初の縦ソートに限っては、要素がバラバラである上
順列検出も必要ないため、こちらはシェアソートで十分に思えます。
あとは、要素が少ない場合はバブルソートでいいでしょう。
どこを閾値にするか難しいですが、一辺が3以下になる16未満としておきます。
よって、改良シェアソートのアルゴリズムは以下のようになります。
- 要素が16未満ならバブルソートを行い、終了する。
- シェアソートを使い、縦ソートを行う。
- 繰り返し回数を求める。（ n = log(√n) ）
- シェアソートを使い横ソートを行う。
このとき、奇数行は昇順、偶数行は降順になるようにする。
- バブルソートを使い縦ソートを行う。
- 縦ソートで、すべての列で交換が発生しない場合、偶数行を反転して終了する。
- 4.～7.を回数分繰り返す。
- シェアソートを使い横ソートを行う。
すべての行で昇順になるようにする。
なお、ここでバブルソートを使っていますが、
クイックソート等の高速ソートだとどうでしょうか。
結論から言うと、シェアソートとクイックソートを組み合わせるより
最初からクイックソートを使った方が速いです。
せっかく改良したのにまさに無駄骨です。