クイックソート

というわけで、昨日宣言しておいたクイックソートを、無理矢理ですが実装してみました。
結果、かなりの力技で組み上げたので、常用するには向かないです。特に、ローカル変数にできないtempとかtempとかtempとか。
C言語みたいにポインタが使えれば、まだマシなの作れるのになぁ。
てか、再帰的処理でポインタ使えないのは、かなり痛いと思うのですが。

ここ２日でバブルソート、クイックソートと作ってみましたが、ちょっとSortコマンドに対抗したくなってきました。
なので、自作のソートサブルーチンでSortコマンドに挑戦していきたいと思います。
ところで、一応あらかじめ断っておくと、ソート「アルゴリズム」ではなく、ソート「サブルーチン」です、ＳＲＣ上で動く「サブルーチン」。
いやはや、流石に全く新しいソートアルゴリズムを作るのは無謀ですからね。あしからず。

当面の目標は、Sortコマンドに、処理時間で勝るソートサブルーチンの作成！
ああ、ちょっと楽しくなってきた。
とりあえず今日は以上です。

以下、クイックソートのソース。

quick_sort:
Local type index elem i j temp2
# ソート対象を決定
If (ArgNum < 2) or (Args(2) = "要素") Then
  # 要素でソート
  type = 2
Else
  # インデックスでソート
  type = 1
Endif

# 配列をソートできるように変換
i = 0
ForEach index In Eval(Args(1))
  Incr i
  temp[i] = "(" & index & ")" & " " & "(" & Eval(Args(1) & "[" & index & "]") & ")"
Next

quick_sort_routine 1 i type

For j = 1 to i
  index = LIndex(temp[j],1)
  elem = LIndex(temp[j],2)
  temp2[index] = elem
Next
CopyArray temp2 Eval(Args(1))
Return

quick_sort_routine:
Local pivot

If Args(1) >= Args(2) Then
  Return
Endif

pivot = partition(Args(1),Args(2),Args(3))
quick_sort_routine Args(1) (pivot - 1) Args(3)
quick_sort_routine (pivot + 1) Args(2) Args(3)
Return

partition:
Local pivot = LIndex(temp[Args(2)], Args(3))
Local left right
left = Args(1)
right = Args(2) - 1

Do while (1)
  Do while (StrComp(pivot,LIndex(temp[left], Args(3))) = 1)
    Incr left
  Loop
  Do while (StrComp(pivot,LIndex(temp[right], Args(3))) = -1)
    Incr right -1
  Loop
  If left >= right Then
    Break
  Endif
  Swap temp[left] temp[right]
  Incr left
  Incr right -1
Loop
Swap temp[left] temp[Args(2)]
Return left