Takenoff Labs » Lotus Script で配列をソートする

[Notes/Domino] Lotus Script で配列をソートする

Lotus Script で配列をソートしたい場面はかなりあると思います。が、標準では残念ながらソート関数は用意されていません。

そこで、大抵の場合、（基数ソートなどを除けば）最も速いと言われるクイックソートのアルゴリズムでソートルーチンを作成すると思いますが、普通に再帰処理でクイックソートを作成すると、ある程度大きな配列でスタックオーバーフローエラーが発生してしまいます(- -;

再帰処理以外でクイックソートを組むのもナンなので、今回は代替案として、比較的新しいソートアルゴリズムである、コムソートを紹介します。

コムソートの仕組みについては、Wikipediaをご覧ください。ここでは、コムソートのメリットとデメリットを列挙します。

メリット

メモリ使用量が少ない（ゆえにスタックオーバーフローは起こらない）
データの状態に左右されず、速度はほぼ安定している。（クイックソートは、データの状態によっては非常に遅くなる。まぁ改良版もあるが）
クイックソートにはかなり負けるものの、バブルソートよりは圧倒的に速い。最近のマシンでは、実用上問題無いレベル。
非常に短く簡潔なコードで書ける。（クイックソートで再帰処理を使用するとファンクションが2つになるが、ファンクションは1つで済む）
コードが短いので、カスタマイズしたい場合（比較処理を変えたいなど）、コピペして少しいじるだけで手軽に対応できる。

デメリット

パッと見で、なぜソートされるのかが理解しにくい。（まぁWikipediaへのリンクを貼っておくとかしておけばいいでしょうが）
クイックソートよりはかなり遅いので、速度が要求される場合は不向き。
リスト変数（連想配列）にはそのままでは適用できない。リスト変数用にカスタマイズするのも、ちょっと面倒？

Notes は、比較的速度が要求されない処理が多いですから、実用上、コムソートで事足りるのではないかと思ってます。わたしは最近コムソートばかり使っています。

ソースコードは、３流（技術屋 and 本読み）さんのサイトにありましたので、そちらを紹介しておきます（Notesでもそのまま使えます）。

http://d.hatena.ne.jp/marujx/20060925

（2009/06/21追記）
わたしはノーツ開発ではハンガリアン記法が好きなので（他の言語ではやらないけど）、変数名を変更したものを記載しておきます。

Public Function ArySort(varAry As Variant) As Variant
	Const COMBGAP = 1.3
	
	Dim varRetAry As Variant
	Dim varTmp    As Variant
	Dim lngMin    As Long
	Dim lngMax    As Long
	Dim i         As Long
	Dim j         As Long
	Dim lngGap    As Long
	Dim blnEnd    As Boolean
	
	varRetAry = varAry
	
	lngMin = Lbound(varRetAry)
	lngMax = Ubound(varRetAry)
	
	lngGap = lngMax - lngMin
	
	blnEnd = False
	
	Do While lngGap > 1 Or blnEnd = False
		lngGap = Int(lngGap / COMBGAP)
		
		If lngGap = 9 Or lngGap = 10 Then lngGap = 11
		
		If lngGap < 1 Then lngGap = 1
		
		blnEnd = True
		For i = lngMin To lngMax - lngGap
			j = i + lngGap
			If varRetAry(i) > varRetAry(j) Then
				varTmp = varRetAry(i)
				varRetAry(i) = varRetAry(j)
				varRetAry(j) = varTmp
				blnEnd = False
			End If
		Next
	Loop
	
	ArySort = varRetAry
End Function