Software Design 2018年2月号

プログラミング コンテスト

~ソートプログラミングの戦い~

はじめに

ZOB Station BBSで行われた「プログラムBASEDコンテスト」の課題2 SORT(並び替え)です。課題1 TAILに続き多くの作品が参加し,高度な内容で実施されました。
ソートプログラムはそのアルゴリズムとその扱うデータによって,実行スピードが大きく異なるため,ソートプログラムコンテストはスピードレースとして非常に興味深いものとなります。
今回は,多種多様なアルゴリズムを実装したソートプログラムによるパワーと技術の激しい戦いが行われ,実行時間という数字で示された結果により,そのソートプログラムの利点や問題点がはっきりと浮き彫りになるコンテストとなりました。

課題2 SORT

指定したテキストファイルを,行単位で文字コード順に並び変えて標準出力に書き出します。ファイルのサイズは 64kbytes未満で,1行の最大文字数は255文字とします。
ANSI Cにおけるqsort関数のような標準で付属しているソート関数は使用禁止です。
MS-DOS付属の SORT のオプションと同じで,標準入力以外にファイル名指定ができる必要があります。

    SORT [/R] [/+n] filename

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

使用言語はC,Pascal,x86 Assembler とします。
ファイルサイズに制限を設けてあるため,オンメモリでデータの並び変えが可能になりますが,そのメモリ管理とデータ構造の扱いには技術と知識が要求され,それによってスピードと動作安定性が変わってきます。
/+nオプションがあるため,「安定」なソートアルゴリズムを使う必要があります。「安定」についてはアルゴリズムの解説を参考にしてください。
今回も課題1 TAILと同様に,各参加者が一般の公開ボードに自分のプログラムの実行ファイルをアップロードする形であったため,先に提出されたプログラムを越えるスピードを実現するためのプログラム技術競争が激しく展開されました。

参加作品

参加作品は 表1 に示すように26本となり,使用言語は C(17本),Assembler(6本),Turbo Pascal(3本)となり,やはりC言語が主流となりました。しかし,スピードに主眼が置かれたコンテストであったので,それを追求するためにオールアセンブラの参加作品もかなりの数集まり,まさにC vs アセンブラの戦いとなりました。
また,募集期間中にソートアルゴリズムの解説や本の紹介が行われたため,参加作品のアルゴリズムは多種多様になりました。安定性の問題についても議論されましたので,安定でスピード的にも優れたマージソートを採用した作品が多かったようです。
また,単一のアルゴリズムには留まらにず,複数のアルゴリズムを融合することにより,それぞれのアルゴリズムの欠点を克服した形の作品も多く見受けられました。

審査内容

審査は以下の3つのテスト+総合点で行ない,(1)動作速度のテストは10点満点,それ以外は5点満点の評価をして合計点で順位づけします。

  1. 動作速度 10点
  2. 安定性+きめ細かな配慮 5点
  3. プログラムソース 5点

(2)安定性+きめ細かな配慮 は課題1TAILと同等なテスト内容となるため,差はあまりないはずです。それに対して(1)動作速度は動作時間による数字の差がはっきりとしており,配点も高いため,このテストで高得点をあげた作品が優位となります。

アルゴリズム

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

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

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

    安定なソートアルゴリズムの例

    • 単純挿入ソート
    • 単純選択ソート
    • バブルソート
    • シェーカーソート

    安定でないソートアルゴリズムの例

    • マージソート
    • シェルソート
    • ヒープソート
    • クイックソート

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

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

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

動作速度テスト

今回のコンテストで一番重要なテストです。このテストの結果上位を獲得したソートプログラムが優位になります。テストで使用するテキストファイルは64kバイト以下で行数が多い必要があるため,かなり苦労しました。

テスト環境
PC9821Ap2 Middle mode i486 20MHz相当
Ratio to the first PC9801 : 28.67

BUFFERS = 20
Quantum LPS540A

テスト使用テキストファイル

TEST1
ZOB Station BBS のメンバーのハンドル(最大半角12文字)5600行 6300bytes のテキストファイルを使用して,オプションなしでNULデバイスに出力
TEST2
ZOB Station BBS のID (zob1????) 6300 行 63000bytes のテキストファイルを使用して /+5 オプションをつけてNULデバイスに出力
TEST3
株価データテキストファイル2159行,62611バイト
数値4桁,スペース1文字,全角文字5文字,スペース2文字,数値4桁,スペース3文字,数値3桁

先頭項目の数値4桁で逆順ソートし,最後のレコードのみを先頭に移動したテキストファイルをオプションなしでNULデバイスに出力

TEST4
TEST3.TXTを第2項目 全角5文字で逆順ソートしたテキストファイルを/+6オプションをつけてNULデバイスへ出力
TEST5
TEST3.TXTを半分にし(1079行),第2項目で正順ソートしたテキストと逆順ソートしたテキストを連結した山型データテキストを/+6オプションでNULデバイスへ出力

以上 5 つのスピードテストを行ないました。
実行時間の合計で順位を決め,速度項目の得点を 5段階で評価しました。
今回はかなりハイレベルの競いあいになったため上位を狙うためにはソートのアルゴリズムだけではなく,入出力とデータ前処理のスピードが大きなウエイトを占める状況になりました。したがって入出力,データ処理をいかに行うかも重要となり上位をアセンブラプログラムが独占する形になりました。しかし,4位のhimesortはC言語ですが,そのアルゴリズムの優位性とコーディング技術の高さにより,アセンブラ作品に割り込む健闘をみてせいます。また,1位rokisort,2位eunosort,3位kumasort,5位masortは,アセンブラプログラムの優位性だけはなく,ソートアルゴリズムの欠点をクリアし,それを効率良く実装した優れた作品です。

安定性,きめ細かな配慮テスト

安定性,きめ細かなテストはいろいろな条件のもと,プログラムの動作が正常に行われるかのチェックをするものです。前回のTAILとほぼ同等なテストなため,問題点をクリアした作品が多かったようです。テストに使用したテキストファイルとテスト方法を以下に示します。

TEST1
65520bytes,8000行のファイルが ソート 出来るかのチェック
TEST2
最後の行の改行コードが無いファイルが ソート 出来るかのチェック
TEST3
64Kbytes超のファイルで 実行した時の動作のチェック
メッセージ表示すれば○
TEST4
行の区切りが LF(0AH)のみのファイルを ソート した時の出力のチェック
TEST5
1行が半角255文字以上のテキストで実行した時のチェック
メッセージ表示すれば○

TEST6
安定性(レコード順に出力するか)のチェック

TEST7
標準入力に対応しているかのチェック
0byteのファイルのチェックも含む
TEST8
フリーメモリ 192Kbyteで 36000byte,6000行のテキストでの動作チェック

評価はスピードテストにおける実行テストも含めています。その結果を表3に示します。
このテスト中ではTEST8の限られたメモリエリアの実行テストが各作品にとって一番きつかったようです。データ構造工夫してスピードアップを図った作品やラージモデルやコンパクトモデルでコンパイルされた作品が多かったため,6割以上の作品が正常動作を行えませんでした。このテストではtakpsortと速度テストでも優れていたhimesortが優れた成績を修めました。

プログラムソース・テスト

■ 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のデータ構造かと思ってしまう可能性があるので注意。

総合結果

動作速度,安定性+きめ細かな配慮,プログラムソースの3つのテストの結果に総合評価を加えてコンテスト順位を決めました。(表4参照) その結果,すべてのテストで優れた結果を残したhimesortが 1位になりました。この作品はラディックスソート,非常にうまい方法で実現しており,テキストを扱うソートプログラムにおいてはベストに近いものと思われます。付録ディスクにプログラムソースが入っていますので是非ご覧ください。

1位 himesort
2位 eunosort
3位 kumasort, masort, rokisort
6位 funasort

の 6作品は大変優れており,参加者のプログラム技術の高さを示していました。
2位,3位の作品はオールアセンブラで書かれており,スピード的には最高速に近い作品です。動作速度テストにおいては0.1秒前後のデッドヒートが行われ,し烈な競争でした。初めはこれらの作品中から1位がでると思われていたのですが,スピードにこだわり過ぎたため,後ろからきたC言語のhimesortに最終的に抜かれる結果となったわけです。
また,6位のfunasortは,ANSI Cの標準関数のみが使われており,スピードより安定性に重点がおかれた作品でTAILに続いて上位入賞を果たしています。