VBScriptで非再帰クイックソート

VBScript版非再帰クイックソートのサンプルとクイックソートと非再帰クイックソートの処理時間の比較。

2014 02 15 あんりあ

前回の『VBScriptでコムソート』でコムソートが遅かったので、非再帰クイックソートを組んでみた。スタックは必要な数を計算して配列を用意する方法にした。

VBScript版非再帰クイックソートのサンプル。

Sub NonrecursionQuickSort(SortArr)
 Dim s, ls(), rs(), l, r, p, pivot, i, j, tmp
 s = Int(Log(UBound(SortArr)) / Log(2)) + 1
 ReDim ls(s), rs(s)
 ls(0) = LBound(SortArr): rs(0) = UBound(SortArr)
 p = 1
 While p > 0
  p = p - 1: l = ls(p): r = rs(p)
  Do While l < r
   pivot = SortArr(Int((l + r) / 2))
   i = l: j = r
   Do
    While SortArr(i) < pivot: i = i + 1: Wend ' 昇順：<、 降順：>
    While SortArr(j) > pivot: j = j - 1: Wend ' 昇順：>、 降順：<
    If i >= j Then Exit Do
    tmp = SortArr(i): SortArr(i) = SortArr(j): SortArr(j) = tmp
    i = i + 1: j = j - 1
   Loop
   If i - l < r - j Then
    If l < i Then
     ls(p) = i: rs(p) = r: p = p + 1
    End If
    r = i - 1
   Else
    If r > j Then
     ls(p) = l: rs(p) = j: p = p + 1
    End If
    l = j + 1
   End If
  Loop
 Wend
End Sub

アルゴリズム的なことはC#によるアルゴリズムとデータ構造がわかりやすい。計測は前回と同じく、乱数データ数6種類の10回平均で比較。計60個の乱数をクイックソート・非再帰クイックソートでソートしてます。