ソート(並べ替え)
単純ソート
 データ数が少なければ、単純なソートで十分でしょう。
 単純なソートの例(sort.as)for HSP2 for HSP3
 けっこう長くなっていますが、実際にソートしている部分は最後のサブルーチンで、10行もありません。
 私の環境(MMX Pentium 200MHz)で、1,000個のデータを1秒、1万個のデータを2分11秒でソートします。
 このソートアルゴリズムは、上から順に、そこから下の最小値を探して入れ替えているもので、選択ソートと呼ばれる場合が多いようです。
 単純なソートで最も有名なのはバブルソートと呼ばれるものですが、バブルソートの無駄かもしれない比較や交換を省いたものが選択ソートで(選択ソートのことをバブルソートと呼んでいる例もあるようです)、ここで使っているものは、さらに無駄かもしれない交換を省いています。

クイックソート
 データ数が多くなると、単純ソートでは時間がかかりすぎるかもしれません。
 無条件・オンメモリではクイックソート(バイナリソート)と呼ばれるアルゴリズムが最速と言われています。
 このアルゴリズムは、適当に選んだ値で全体を2つの部分に分け、上の方にはその値以下のもの、下の方にはその値以上のものを置き、それぞれの部分について、再び同じことを繰り返す──というのを部分が1要素になるまで繰り返すものです。
 ただ、件数が多くなると、アルゴリズムは同じでも、やり方によってけっこう大きな速度差が出てきます。私の知っている限りでは、10年以上前の月刊アスキーに掲載されたBASICプログラムが最速で、それをHSPに移植・改造したリストがありますが、公表していいものかどうか、よくわかりません。
 それよりは多少遅いのですが、クイックソートのサンプルを作りました。
 クイックソートの例(qsort.as) for HSP2 for HSP3
 1万個のデータを2秒、10万個を18秒(アスキー版は13秒)でソートします。

 なお、データが一定の条件を満たしている場合は、クイックソートより速いアルゴリズムもあります。例えば、度数分布表を作ることができるようなデータなら、それを作り、それに基づいてソートするのが最も速くなります。

インデックスソート
 一方、「単純に数値配列をソートすればいい」という場合は、寧ろ少なくて、あるデータの大小によって、複数のレコード(複数の項目からなる1件のデータが複数個集まったもの)をソートしたいという場合がほとんどでしょう。その場合、クイックソートでもけっこう長い時間がかかったりします。
 そういう場合は、データそのものはソートせず、データのインデックスをソートするインデックスソートが有効になります。
 インデックスとは、「ソート結果のn番目のデータは元のデータの何番目か」を記憶する配列です。
まず、インデックスを次のように初期化します。
#define NUM_DAT     ;データ数
    dim index,NUM_DAT
    repeat NUM_DAT
        index.cnt=cnt
    loop
 そうして、ソートにおいて、通常はi番目のデータとj番目のデータを比較するところを、index.i番目のデータとindex.j番目のデータを比較します。また、データを入れ替えるところでは、i番目のデータとj番目のデータを入れ替えるかわりに、index.iindex.jを入れ替えるのです。
 ソートが終わったら、通常はi番目のデータを参照するところを、index.i番目のデータを参照するようにします。

最も速いのはソートしないこと
 当然ながら、ソートせずに済ますことができれば、それが最も速いのです。
 データを追加するときに、それが入るべき位置に挿入するようにすれば、いちいちソートする必要はありません。このとき、挿入する位置より後の部分をずらさなければなりませんが、インデックスを使えば、やはりスピードアップすることができます。

ホームページ HSP