ソートに挑戦

そもそもがNScripterでスタックだ再帰だなんだと言いだしたのは、その技術が有用だ、と言うのもあるが、ソート、つまりは配列の並び替えをしたいと言う欲求もあったはずなのだ。再帰の必要なクイックソートとかね。
それで、wikipediaをだらだら見ていたら、「バケツソート」とその応用の「基数ソート」なんてのを見つけて、これはもう、言われてみればああそうだねと言うようなわかりやすいアルゴリズムだった。
基数ソート - Wikipedia

基数ソート、俺解釈

10個のバケツを用意し、それぞれに0〜9の番号を振る。
配列には数字が入っているが、それらの桁数の最大値は決まっている。あとついでに全て0以上の整数としておく。
配列の頭から順に数値を取っていく。取った数値の最後の桁に注目し、その値をその番号のバケツに放り込む。バケツは、放り込まれた順番を記憶しているから、正確にはバケツじゃないのかも。
全部放り込んだら、バケツの中身を0から9の順番につなぎあわせて新しい配列にする。（降順なら逆に9から0へ）
この新しい配列に対し、さっきの要領で再びバケツに放り込んでいくが、今度は下から2番目の桁に注目して振り分けて行く。
これを繰り返して最大桁数までやってしまうと、最後に残った配列がソート後の配列になる。

評価

• 安定ソートである。つまり、同じ値があった時に順序が入れ替わったりしない。
• 計算量が常に一定である。配列の長さ*桁数で決まる。すると、速度について考えるのが一回で済む。
• そして何より、アルゴリズムがわかりやすい。

NScripterで使う場合の利点

デフォルトの配列変数を使うのではなく、文字列変数を疑似的に可変長配列として扱う場合、ネックになるのが配列の要素の位置の交換操作であり、このアルゴリズムはそれをしなくて済むと言う点で利点である。
必要なのは、先頭から一つ要素を取りだし、元の配列を一つ短くする操作と、配列の最後に要素を追加する操作だけである。特に後者はデフォルトの機能がそのまま使えるので、新規開発も少なく、つまりはバグの入り込む余地も少なくできる。
それにスタックを使わないので、使用する変数領域を固定にできる。

使い道

もっとも、ソートで本当に数値そのものを並べ変えたいと思ったりすることはまずない。
実際のプログラムでは、複数のオブジェクトを、任意のプロパティをキーにして並べ替えると言う場合がほとんどだ。
ファミコンとかでRPGやってりゃわかるけど、「パーティメンバー候補をレベルの高い順に並べる」とかザラにあることだ。
そんな訳で、NScripterで実装するのは、前提としてオブジェクト指向なデータ構造がないといけないと言うことに。

他の言語の場合

sortとか普通にあるから、いちいちこんなの考えるこたねーよ。