シェーカーソート - abwiki @ ウィキ (ActiveBasic非公式wiki)

整列アルゴリズムのひとつ。
改良交換法、双方向バブルソートとも呼ばれる。名前のとおりバブルソートの改良型である。バブルソートでは隣り合う2つのデータを順次比較するため、整列したデータでも比較する必要があった。そこで最後に比較した位置を記憶し、バブルソートの走査方向を逆転させることで、次回に比較整列する範囲を縮小させ、無駄な比較を減少させている。

プログラミング掲示板「ソートロジック大会」なども参照のこと

TypeDef keytype = Integer
Sub shakersort(n As Integer, a As *keytype)
Dim i As Integer, j As Integer, k As Integer
Dim x As keytype
Dim left As Integer, right As Integer, tmp As Integer
left = 0 ' 整列する範囲の左端
right = n - 1 ' 整列する範囲の右端
While left < right
' 左から右にバブルソート
For i = left To right
If a[i] > a[i + 1] Then
j = i + 1
x = a[i]
a[i] = a[j]
a[j] = x
tmp = i
End If
Next i
right = tmp
' 右から左にバブルソート
For i = right To left Step -1
If a[i] < a[i - 1] Then
j = i - 1
x = a[i]
a[i] = a[j]
a[j] = x
tmp = i
End If
Next i
left = tmp
Wend
End Sub