SORT [/R] [/+n] filename

    /R  並べ換え順の逆順; Z から A， 9 から 0 の順にします.
    /+n n 桁以降の文字によるファイルの並べ換えを指定します.

アルゴリズム

• 「安定」なソートについて

「安定」なソートというのは，比較結果が等しいとされる要素の配列内での前後関係を，ソート前とソート後で入れ換えることがないものをいいます。

ソート前	ソート後
	安定	安定で無い
01BBB	02AAA	02AAA
02AAA	01BBB	03BBB
03BBB	03BBB	01BBB

ソート前のデータを/+3でソートした場合，「安定」なソートと「安定」で無いソートは以上のような結果になります。
安定でないソートを用いた場合，例えば dir | sort /+10 としたときに拡張子が同じファイルは，ディレクトリエントリの順にはならないことになります。

安定なソートアルゴリズムの例
• 単純挿入ソート
• 単純選択ソート
• バブルソート
• シェーカーソート
安定でないソートアルゴリズムの例
• マージソート
• シェルソート
• ヒープソート
• クイックソート

スピードが速いアルゴリズムは安定でない，というの傾向があるようです。しかし，文字列として比較した結果が一致したときに入力内での位置を比較するようにすれば，安定でないソートアルゴリズムを安定なソートアルゴリズムにすることができます。

• クイックソート

ソートのアルゴリズムといえば，クイックソート(LIST 2)がまず上げられます。スピードが速く，コーディングも楽でスタックエリア以外のワークエリアも必要としないため，かなり広く使われており，ANSI Cの関数としても採用されています。
しかし，このソートアルゴリズムには欠点が２つあります。そのひとつは，大小分割の基準となる要素が全体データの中央値からどの程度離れているかにより，スピードが大きく異なり，再帰の深さも変化することです。基準要素が最大値や最小値に近い値ですと再帰呼び出しが深くなるため，スピードが落ち込み，消費されるスタックも多量となり，スタックオーバーフローが発生する可能性もでてきます。
２つめの欠点は「安定」ではないことです。比較要素が等しい場合，配列における位置がソートの前後で変化してしまう事は，同じ要素が多く含まれるデータでは大きな欠点となります。
しかし，わずかな改良でこれらの欠点はクリアできます。まず一つめの基準要素の欠点は，要素をいくつか選びその中での大小関係の中央値を使うことで解決できます。LIST 3では配列の1/4，1/2，3/4に位置するデータの中央値を選びだし，それを基準要素として使っています。ただこの3つのデータがすべて最小値，最大値に近いものですと，意味がなくなります。したがってこのデータが多ければそのような危険性は減少するわけですが，データ多いとその中央値を得るための時間がかかることになり，かえって無駄な処理となりますので，この辺のバランスが難しいところです。
LIST 3のソート関数では，ソートデータ数が少ない場合は，中央値を求める処理時間の比重が増大しますので，その場合はソートを行わないでリターンするようにしてあります。また，クイックソートは少ないデータのソートは得意ではないためこのような判断は，さらなるスピードアップにつながりますが，クイックソートからリターンした時点では完全なソート済みのデータにはなっていません。そこで，そのデータを非常に簡単な単純挿入ソート(LIST 1)で仕上げのソートを行っています。単純挿入ソートはアルゴリズムが分かりやすく，コーディングも楽なのですが，スピード的に遅いソート法です。しかし，このソートは整列がある程度されたデータのソートでは，その隠された力を発揮して非常な高速なソートに変身します。したがって，このような使用方法には最も適したソート法ということができます。
２つめの欠点の克服は，比較した結果が同じデータのときは，そのデータの入力時の位置をチェックする処理をつけ加えることで解決できます。LIST 3では，if文を加えて，このチェックをおこない「安定」なソートへの改良を行っています。

• ラディックスソート

ラディックスソート(基数整列法)は，文字(キャラクタコード0～255)の頻度を求める事により，行ポインタをキャラクタコード順に入れ替えて整列を行います。これだけでは，先頭の１文字のみのソートしかできませんが，最終文字から前の文字に向かって１文字ずつソートを行えば 後ろの文字のソート結果が前の文字に反映するため，先頭文字の処理
を終了した時点で行のソートが完成します。
すべての行が同じ文字列長のテキストファイルのときには，効率が非常に良いのですが，文字長が異なる場合，実現することは難しいソートアルゴリズムです。
ラディックスソートは，ソート対象となる文字列長がすべて同じテキストデータのソートにおいては，最高速なソート法に分類されます。
今回のコンテストで扱うデータはテキストデータですので，ラディックスソートが得意なデータ構造に近いため，このアルゴリズムを実装したソートプログラムがあれば好成績になることが予想されました。しかし，一般的なテキストファイルは行の長さにはまちまちであり，単純なラディックスソートのみでは完全なソートプログラムにはなりません。
LIST 4は行の先頭の2文字のみをラディックスソートで並び変え，LIST 3の改良版クイックソートと同じ様に，単純挿入ソートで仕上げを行う必要があります。

• 動作速度テスト結果

コンテストで行った動作速度テストと同じテストを各ソートに対して行ってみました。
1.単純挿入ソートのみは，ほとんど整列が行われているテキストを対象にしたソートテストを付け加えてみました。この動作速度テストは入出力の時間がかなりの占めるため，ソートを行わないで入出力のみを行った時間を5.に示しました。この値を差し引いたものがソート処理に要した時間と考えてみてください。

		TEST1	TEST2	TEST3	TEST4	TEST5	TEST6
1	単純挿入ソート	57.58	89.76	36.63	33.38	16.54	1.25
2	クイックソート	2.96	3.17	1.50	1.48	14.68
3	改良版クイックソート	2.87	3.15	1.48	1.45	1.56
4	ラディックスソート	2.47	5.34	1.94	1.77	1.46
5	入出力に要した時間	2.08	2.34	1.24	1.24	1.23

2. クイックソートは山型データを使用したTEST 5では，非常に時間がかかり，1.単純挿入ソートは整列したデータにおける速さが圧倒的に速いことがわかります。

■ BOSSORT (C)　[3]
マージソートでの参加であるが,各種ソートアルゴリズムのテストを含むデバッグ行が多く残されているため実質的なソースは全体の半分程度という,非常に読みにくいソースになってしまった。入出力にdos_read,dos_write関数を使用しているので,処理速度は同じアルゴリズムのOGUSORTを若干上回る。今回もまたポインタが多く使用されているが,もう少しポインタの使い方を洗練させて欲しい。

■ EUNOSORT (ASM) [4]
クイックソートと挿入ソートを組み合わせたものである。枢軸(問題分割の境目となる要素)には,中間と1/4と3/4に位置する三つのデータを比較してその中央値を使用しているため,スピードテスト5のような山形データにおいても処理速度が落ちない。また問題規模が小さくなってからは挿入ソートに切り替えるなど,クイックソートの問題点をよくカバーしている。各行の文字数を1バイトのデータとして行の先頭位置に格納しているので文字列比較が速度的に有利となるが,256文字以上の行は扱えないことになる。EUNOTAILに比べMASM6ディレクティブの使用方法が良くなっているが,更に使い方を極めてほしい。

■ EXITSORT (C) [3]
再帰を使わずに明示的なスタック操作でクイックソートを実現している。SMALLモデル用としたためFAR指定が多く,変数名も長いことから全体的に見にくいコーディングとなっている。クイックソートでは枢軸を決める方法が非常に重要だが,このソートでは単純に先頭のデータを枢軸として利用するため,データの並び順によっては極端に動作速度が落ちることになってしまった。

■ FERSORT (TURBO PASCAL) [2]
シェルソート。Turbo Pascalでサポートする文字列の欠点が出て,文字列へのポインタをシンプルに書けていない。また各所で文字列転送のオーバーヘッドが生じて速度低下の原因となってしまっている。Turbo Pascalで文字列処理を行う場合は,どこまで標準関数に頼るか自前で書くか難しいところだ。また変数名が簡単すぎて読みにくいところがあるので再考して欲しい。

■ FUNASORT (ANSI C) [4]
マージソートをオーソドックスなコーディングで実現している。固定長テキストバッファにテキストを読み込むと,テキストの行ポインタテーブルを確保し,このポインタを入れ替えることによりソートを行う。ANSI C標準関数のみを使用しているため入出力処理がやや遅いが,動作が安定していて可搬性も高い。

■ GESISORT (C) [2]
fgetsで1行ずつ読み込むと文字列へのポインタ配列を挿入ソートする。関数のインタフェイスがコメントされているのは良い点だが,メイン関数はやや長めなのにもかかわらず改行が多いので制御構造を一目で把握しにくく,残念である。また記憶クラスやメモリモデルが余り意識されていないのか,変数の使い方が少々不自然になってしまった。自動変数で大きな配列を確保してしまっているのもtailから変わっていない。

■ HAYASORT1(C) [3]
先頭2バイトのラディックスソートのあと挿入ソートで仕上げる。先頭2文字が同じ文字や数字データだとラディックスソートの段階で荒く整列させることができず,処理速度が落ちる。

■ HIMESORT (C++ as better C) [5]
ラディックスソートは文字列のソートにおいて威力を発揮するが,各行の文字数がまちまちな実データに対してそれを適用するのは難しい。このプログラムでは,まず各行を文字数をキーにしてソートして(ここでは1段のラディックスソートと挿入ソート)文字数が揃った塊を作ってから適切な矩形領域を設定してラディックスソートを繰り返し適用する,という手法を用いることにより,非常に高速なソートを行うことに成功している。入出力にfread,fwrite関数を利用しているにもかかわらず,この処理速度を実現していることは素晴らしい。テキスト行ポインタを格納する配列を固定長でグローバル変数として確保している部分にやや難がある。

■ IKESORT (C) [3]
再帰版クイックソート。バッファにテキストをまとめて読み込んでから各行へのポインタテーブルを生成し,これをソートする。クイックソートでは,単に中央に位置する要素を枢軸に選ぶのはリスクが大きい。要素数が少なくなったら選択ソートを行なう部分は条件コンパイルでオフ。ソースの方は今回コメントが減ったのは惜しいが,簡潔で動きは追いやすい。読み込んだテキストの終端の処理で=と==演算子の単純なミスがあるなど,前回の出来に比べ煮詰める時間がなかったという印象が強い。

■ KENSORT (C) [3]
非再帰版クイックソートで荒く列べ,挿入ソートで仕上げる。このクイックソートでは単に中央に位置する要素を枢軸に選ぶため,スピードテスト5のようなデータで遅くなる場合がある。ソースはコメントが少ない割りには流れが追いやすい。fgetc,fputcによる1文字単位の入出力と,FARポインタ演算の多様とは,比較的凝ったアルゴリズムを採用しているにもかかわらず全体に無視できない速度低下をもたらしている。

■ KMOSORT (C) [3]
マージソートをリスト構造を使って実現している。(ただしリストのノードは配列風に最初に一定個数が確保される。)SMALLモデルであるためfar_関数が多用されており,全体的に簡潔さに欠ける。また入出力にfgets,fputs関数を使っているのでスピードの点でやや劣る。前課題のKMOTAILに比べプログラム技術の大きな向上が見られ,課題3に期待が持てる。

■ KMSORT (C+ASM) [3]
再帰版クイックソートで,単に中央に位置する要素を枢軸に選ぶ。いくつかのプリミティブな処理をアセンブリ言語で書いている。関数名がやや漠然としているものがあり,コメントもないので処理内容がすぐには解らないのが残念。動作も不安定のようだ。

■ KUDSORT (ASM) [3]
作者からはバブルソートと説明されているが,全体の処理の流れを見ると,1文字目が同じである行のグループ,1文字目も2文字目も同じである行のグループ……のようにどんどん分類を細かくしていく分割統治手法を用いており,広義のラディックスソート(基数交換法)になっている。その分類の過程でバブルソートを用いている。ソースはアセンブリ言語のせいか,データ構造やアルゴリズムに関わる部分のコメントが解りにくいか,あるいは足りないようだ。

■ KUMASORT (ASM) [4]
非再帰版のクイックソートと挿入ソートを組み合わせという,EUNOSORTと同様のアルゴリズムである。クイックソートの枢軸には,先頭と最後と中間点の三つのデータを比較しその中の中央値を使っている。また部分問題が小さくなったら挿入ソートに切り替えることにより,クイックソートの欠点を解消している。EUNOSORTと違って行の文字数を保持していないため比較のたびに文字数を取得しなければならず,速度的にROKISORT,EUNOSORTにやや劣ることになるが,本プログラムのアルゴリズムが汎用に用いられるものとしてはベストに位置するものと思われる。

■ LALFSORT (C) [3]
マージソートをリスト構造を利用して実現している。そのためやや複雑なソースとなっているが,そのことがあまりメリットになっていない。行入力毎にmalloc関数でメモリエリアを確保していることから入出力が遅くなっている。また文字列比較にjstrcmp関数を利用しているので2バイト文字の比較も確実に行える。前課題のLALFTAILのような簡潔が失われたことは残念である。

■ LIZSORT (TURBO PASCAL) [1]
アルゴリズムは選択ソート。データセグメントに5000行分の文字列へのポインタ配列を有するが,文字列の実体を格納するためのメモリを確保せずに読み込みを行っているためまず間違いなく暴走する。New(ReadBuf[n]); の一行を入れれば(まだバグがあるものの)一応ソートを行うようになるだけに惜しい。ポインタの概念を理解してもらいたい。

■ MASORT (ASM) [4]
ヒープソートをアセンブリ言語で実現しており,トークンをサポートするなど機能が高い。ヒープソートはクイック,ラディックスソートに比べて速度的にやや劣るのが残念であるが,記憶領域の点では有利なアルゴリズムである。アセンブリソースはオーソドックスなTINYモデルのものであるが,ラベル名にもう少し工夫がほしい。また変数領域がコードセグメント内で最後尾に位置しているが,データセグメントを前にして変数領域とし,コードとデータセグメントを同一グループにするコーディングにもチャレンジしてほしい。

■ MIOSORT (TURBO PASCAL) [3]
入力時に各行をノードとする2分探索木を構築して,出力時にこれを中央順(inorder)に走査してソート結果を得る。2分探索木へのノードの挿入にはノードの平均の深さに比例した時間がかかり,最悪(ソート済みの順でデータを入力するなど)の場合の性能が悪くなるのでここに少々工夫が施されている。ソースにはDEBUG行が残されており,インラインアセンブラも使用されているので,Pascalにしてはソースが読みにくい。文字列比較処理がインラインアセンブラで書かれているが,Pascalでは通常の比較演算子にのみで文字列比較が行われるのでそれを利用したほうが良い。

■ MISSSORT (C) [3]
マージソート。SMALLモデルを利用しておりCの標準関数がNEARポインタになるため,FARポインタで処理するための関数を独自に用意している。これが処理速度低下の原因となっている。またメモリ確保にDOSのファンクションコールを利用したり,文字を検索するための関数をわざわざ作成している。Cの標準関数をもっと有意義に利用する方法を考えるべきである。

■ NAZSORT (C) [2]
比較先頭位置の文字コードについて1発バケットソートを行ってから,それぞれのバケットに対しバブルソートをかける。一つ一つの関数が長く,データ構造も単純ではないのでこのままでは流れを把握しづらい。不具合があってもなかなか追い切れないようであるが,まず機能分割をしてスッキリさせた方がよいだろう。

■ OGUSORT (C) [4]
FUNASORTと同様なマージソートであるためソート関数部分はほとんど同じである。入出力にread,_write関数を使用しているため動作スピードはFUNASORTに比べて速くなっているが,行ポインタの設定や比較処理でやや問題点が見える。

■ ROKISORT (ASM) [3]
基本的には非再帰版のクイックソートなのだが,ROKISORT3では先頭文字によるバケットソートを行った後クイックソートを行っている。行ポインタの他にチェインデータが設定されており,更に行文字数を2バイトのデータとして行先頭の前に格納している。枢軸としては,最初の分割時のみ各行の2文字目のデータでテーブルを作り中央値に近い値を求め,以後の分割では真ん中に位置する要素を採用しているが,これでは速度低下が起こる場合がある。
スピードアップのためのコード自己書き換え部分が多くあり,486等のCPUキャッシュを使用するものでは動作の不安が残る。今後のCPUの動作から考えると自己コード書き換えは更に危険で意味の無いものとなるので,できるだけ行わないようにしてほしい。ROKISORT3は速度重視のため,かなり見難いソースとなっている。ROKISORT2の枢軸決定部分のみを書き換えた方が良かったのではないか。

■ SAWASORT (C) [3]
挿入ソート。ソースは全体にシンプルだが,変数名の命名の仕方がハンガリアン記法に独特の変更を加えたものなので,変数の利用目的が一言説明されているとより他人にも読みやすくなるだろう。

■ SHISORT (C) [4]
再帰版クイックソートで,単に真ん中に位置する要素を枢軸に選ぶ。元のテキスト以外に整列オプションに合わせて加工したテキストもメモリに保持している。この加工文字列でオプションと安定化の仕組みを吸収しているため,オプションが多彩でもクイックソートの関数は基本的な最低限のコードのままになっているのが面白い。しかし速度面ではわずかながら不利になった。

■ TAKPSORT (C) [3]
シェルソートをベースに,レコード順が崩れないような安定化の処理を行っている。全体に安定した動作をするようにコーディングされているが,その反面スピード的に劣る書き方が目立つ。例えば1箇所でのみ用いる変数の入れ替えのために関数をコールするのはちょっと行きすぎではないだろうか。また入出力においてfgets,fwriteと共に一時的な文字列バッファを使用しているので,処理速度が低下している。

■ TUNASORT (C) [2]
選択ソート。要素の交換はポインタの交換で実現しているが,最小の要素を見つけるたびにその文字列全体をコピーして比較に利用している。この処理には余分な時間がかかるので,これもポインタで管理すべきである。

■ UISORT (C) [3]
バブルソートと説明されているが,実際には1行ずつソート済み双方向リストに追加していくアルゴリズムなので挿入ソートと言った方がいいだろう。ただし先に比較開始位置の文字コードによるバケットソートで大まかに分類する。1行ごとにmallocして処理するのは速度面でやや不利。またソースでは双方向リストを「キュー」と書いているが,読み手がFIFOのデータ構造かと思ってしまう可能性があるので注意。