Posted: 2005年9月29日(木) 02:21
＞このソートのアルゴリズム名は？
度数ソートの変形。
というか、08月27日(土) に私が書いたQuicksort改４と方針は同じ。
＞前提条件
＞ホストコンピュータ又はCOBOLで作成したデータをソートする用途向きの簡略版です。？
「ホストコンピュータでFORTRANで作成したデータ」というのは、
・ホストコンピュータ又はCOBOLで作成したデータ
という条件を満たしていますが、ソートできませんよ。
理由：FORTRANでは数値の最高位より左の桁はゼロでなくスペースとなる。コレに対応していない。
また、Ｅ変換やＧ変換で書き出したデータは、左から判断していく方法ではそもそも整列できない。
COBOLで作成した数値データでも、マイナスがあった場合には対応していない。
N88BasicやQuickBasicでは、基本命令の動きの違いで、このプログラムは動きません。
Function GigaSort(xNo As Integer, xFileName As String)As Integer
：
FN=Wk + Str$(j)
まず、コレがアウト。
jは０～９のいずれかというのがプログラムの要請ですが、
Str$(0)=" 0"
となるから、ファイル名にスペースが割り込んでしまうのでDOSではダメ。
ここは、
FN=Wk + Hex$(j)
Sub SortOut(xFileName As String)
Open xFileName For Input As #1
Field #1, LineLength 'バイト数
While (Eof(1)=0)
Get #1, -1, StrBuf
Put #2, -1, StrBuf
ファイル操作については、全くのMicrosoftBasic非互換といってもよいでしょう。
Open xFileName For Input(OUTPUT/APPEND)
というふうにシーケンシャルモード（テキストファイルモード）でファイルをOPENした場合、
FIELD文やGET(PUT)文は使えません。
また、ランダムファイルとしてOPENしたとしても、
Open xFileName As #1 LEN=Linelength （または OPEN "R",#1,xFileName,Linelength)
' ↑この構文はN88Basic不可。N88はLEN=256に固定。
Field #1, LineLength as StrBuf
for rec=1 to LOF(1)/Linelength '（ N88はfor rec=1 to LOF(1) ）
Get #1
Lset StrBuf2=StrBuf2 '← Field #2, LineLength as StrBuf2と宣言してあるとして。
Put #2
と、こうなります。
あと、メモリー内に引き込めないほど多量のデータをソートするときは、
普通はマージソート（外部ソート）を使います。
「外部ソート」or「バランスウェイマージソート」or「ポリフェーズマージソート」
で検索してみてください。
大まかなやり方は以下のとおり。
１．メモリーに引き込めるだけのデータを読み込み、ソートしてからファイルに書き出す。
（ソートアルゴリズムはクイックなりヒープなり、速いものならどれでも可）
２．まだデータが残っていれば、１．を繰り返す。
３．ファイル同士でマージソート。
こうすることで、データの特殊性に依存せずソートできますが、
・度数ソート、逆写像ソート、ラディックスソートはＯ(n)
・マージソート、クイックソート、ヒープソートはＯ(nlogｎ)
であるので、一般論としては、度数ソートでokなら度数ソートのほうが速いといういことになります。
omasuさん 09月24日
＞①．一番遅いはずの、バブルの進化がクイックソート？。
そのとおり。
＞②．シェルソートは、選択法で作ると遅い、挿入法だとなぜか早い。
選択法で作ったシェルソートというのは聞いたことないです。
また、私のコーディングは、挿入法ベースですけど。
選択法の進化系ですが、
最小（大）値選択法－トーナメント法－ヒープ。
※トーナメント法：
勝ち抜き戦で１位を決めるにはｎ－１試合必要。では、２位を決めるには？
改めて残りチームで勝ち抜き戦をやっているのが最小値選択法。
でも、１位に負けたチームだけ、元のトーナメント表どおりに
試合すれば２位は決まるから、logｎ回で２位は決まります。
３位以下も同様。よって、ＮｌｏｇＮでソートできることの証明終わり。
交換法（バブル）を元にしたシェルソートというのなら存在します。
共立出版 「プログラム書法、1976」 B.W.Kernighan and P.J.Plauger P191
から言語を変換(元はFORTRAN)し、コメントを追加したもの。
SUB SHELL(X(),N)
IGAP=N
DO WHILE IGAP>1
IGAP=IGAP/2 'shell
' IGAP=IGAP/1.3 'comb
IMAX=N-IGAP
DO
IEX=0
FOR I=1 TO IMAX
IPULUSG=I+IGAP
IF X(I)<=X(IPULUSG) THEN
W=X(I) : X(I)=X(IPULUSG) : X(IPULUSG)=W
IEX=1
END IF
NEXT
LOOP WHILE IEX=1 'shell
' LOOP WHILE IGAP=1 AND IEX=1 'comb
LOOP
END SUB
※REM文２箇所を入れ替えるとコムソート。
＞③．単純挿入法はバイナリサーチで挿入ポイントを決めると早い。
交換回数は単純挿入法と等しいから、手間をかけた割には速くならない
というのが通常の評価です。
また、シェカー法というのは輪をかけてとんでもない方法で、反面教師としてしか使えません。
シェル法以上に複雑なプログラムですが、単純挿入法にすら勝てないから。
＞シェル法のギャップのとり方
1,4,13,....M,3M+1 の他に、
1,3,7,15...M,2M+1 とか、（これもクヌース大先生おすすめ）
IGAP=IGAP*0.45 ※最後はIGAP=1を実行するのをお忘れなく。
というのもおすすめ品。
＞いろんなロジックを教えてください。
単純挿入法ベースのコムソート（コムソートの性格上、最後の仕上げがバブルでないだけ。）
IGAP=N
WHILE IGAP > 2
IGAP = IGAP *10 \ 13
FOR i = IGAP + 1 TO N
J = i - IGAP
IF Key(i) < Key(j) THEN
W=Key(i) : Key(i) = Key(j) :Key(j)= W
End If
NEXT
WEND
For i=2 to N
X=Key(i) : Key(0)=X
j=i-1
While X<Key(j)
Key(j+1)=Key(j): j=j-1
Wend
Key(j+1)=X
Next
マティさん 09月24日
＞クイック派に転向
そう単純に割りきれないところがあります。だからヒープ派というのが厳然として存在。
（私はシェル派なんだけどね。）
クイックソートには欠点があり、
X=Key((L+R)\2)
とした場合、元データがたとえばこういう場合にボロボロになります。
＜1 3 5 7 9 10 8 6 4 2 ＞ （両端に小さい数、真ん中に大きい数。）
最悪時にはスタックオーバーで自爆。自爆しないためには、08月27日の私の記述の改１。
ただし、これだけでは、ｎ^2の時間がかかってしまうので、解除（厳密な解除ではない）には改３が必要。
>バブルソートの進化系はコムソート
バブルソートの最終進化系はクイックで間違いありません。
コムソートは、単純挿入法改もアリ。そして、バブルソート改より速い筈。（キーの長さが短かいならば。）
なお、個人の趣味（＝美意識）になってしまうけど、
omasuさんのように、
'単純挿入法
For i=1 To E
For j=i To 1 Step -1
If KeyTable(j)<KeyTable(j-1) Then
Swap KeyTable(j),KeyTable(j-1)
Else
Exit For
EndIf
Next j
Next i
というのは組む気ナシです。
単純挿入法は、あくまで、
For i=2 to N
X=Key(i) : Key(0)=X
j=i-1
While X<Key(j)
Key(j+1)=Key(j): j=j-1
Wend
Key(j+1)=X
Next
であって、Exit Forのようなムナくそ悪い「例外処理命令」は使いたくないです。
Zgockさん 09月29日
＞２回に分割する場合、バケツソート（注：度数ソート）に比べて速度は２倍、ワークは１００分の１
速度は１／２です。
＞クイックソートは速いアルゴリズムで非常に美しいですが、
＞安定じゃないのだけが欠点ですね。
＞そういう理由からヒープソートをよく使います。
これって、「ヒープソートは安定である」という意味にしか解釈できないのですが。
でも、ヒープソートって安定なんか？
平成１５年度ソフトウェア開発技術者試験午前問13では、「ヒープソートは安定ではない」
が正解なんですけど。
http://sinzo.web.infoseek.co.jp/joho/so ... 03_01.html
クイックソートは、「n^2の時間がかかる数列が存在する」
というのが最大の欠点でしょ？
度数ソートの変形。
というか、08月27日(土) に私が書いたQuicksort改４と方針は同じ。
＞前提条件
＞ホストコンピュータ又はCOBOLで作成したデータをソートする用途向きの簡略版です。？
「ホストコンピュータでFORTRANで作成したデータ」というのは、
・ホストコンピュータ又はCOBOLで作成したデータ
という条件を満たしていますが、ソートできませんよ。
理由：FORTRANでは数値の最高位より左の桁はゼロでなくスペースとなる。コレに対応していない。
また、Ｅ変換やＧ変換で書き出したデータは、左から判断していく方法ではそもそも整列できない。
COBOLで作成した数値データでも、マイナスがあった場合には対応していない。
N88BasicやQuickBasicでは、基本命令の動きの違いで、このプログラムは動きません。
Function GigaSort(xNo As Integer, xFileName As String)As Integer
：
FN=Wk + Str$(j)
まず、コレがアウト。
jは０～９のいずれかというのがプログラムの要請ですが、
Str$(0)=" 0"
となるから、ファイル名にスペースが割り込んでしまうのでDOSではダメ。
ここは、
FN=Wk + Hex$(j)
Sub SortOut(xFileName As String)
Open xFileName For Input As #1
Field #1, LineLength 'バイト数
While (Eof(1)=0)
Get #1, -1, StrBuf
Put #2, -1, StrBuf
ファイル操作については、全くのMicrosoftBasic非互換といってもよいでしょう。
Open xFileName For Input(OUTPUT/APPEND)
というふうにシーケンシャルモード（テキストファイルモード）でファイルをOPENした場合、
FIELD文やGET(PUT)文は使えません。
また、ランダムファイルとしてOPENしたとしても、
Open xFileName As #1 LEN=Linelength （または OPEN "R",#1,xFileName,Linelength)
' ↑この構文はN88Basic不可。N88はLEN=256に固定。
Field #1, LineLength as StrBuf
for rec=1 to LOF(1)/Linelength '（ N88はfor rec=1 to LOF(1) ）
Get #1
Lset StrBuf2=StrBuf2 '← Field #2, LineLength as StrBuf2と宣言してあるとして。
Put #2
と、こうなります。
あと、メモリー内に引き込めないほど多量のデータをソートするときは、
普通はマージソート（外部ソート）を使います。
「外部ソート」or「バランスウェイマージソート」or「ポリフェーズマージソート」
で検索してみてください。
大まかなやり方は以下のとおり。
１．メモリーに引き込めるだけのデータを読み込み、ソートしてからファイルに書き出す。
（ソートアルゴリズムはクイックなりヒープなり、速いものならどれでも可）
２．まだデータが残っていれば、１．を繰り返す。
３．ファイル同士でマージソート。
こうすることで、データの特殊性に依存せずソートできますが、
・度数ソート、逆写像ソート、ラディックスソートはＯ(n)
・マージソート、クイックソート、ヒープソートはＯ(nlogｎ)
であるので、一般論としては、度数ソートでokなら度数ソートのほうが速いといういことになります。
omasuさん 09月24日
＞①．一番遅いはずの、バブルの進化がクイックソート？。
そのとおり。
＞②．シェルソートは、選択法で作ると遅い、挿入法だとなぜか早い。
選択法で作ったシェルソートというのは聞いたことないです。
また、私のコーディングは、挿入法ベースですけど。
選択法の進化系ですが、
最小（大）値選択法－トーナメント法－ヒープ。
※トーナメント法：
勝ち抜き戦で１位を決めるにはｎ－１試合必要。では、２位を決めるには？
改めて残りチームで勝ち抜き戦をやっているのが最小値選択法。
でも、１位に負けたチームだけ、元のトーナメント表どおりに
試合すれば２位は決まるから、logｎ回で２位は決まります。
３位以下も同様。よって、ＮｌｏｇＮでソートできることの証明終わり。
交換法（バブル）を元にしたシェルソートというのなら存在します。
共立出版 「プログラム書法、1976」 B.W.Kernighan and P.J.Plauger P191
から言語を変換(元はFORTRAN)し、コメントを追加したもの。
SUB SHELL(X(),N)
IGAP=N
DO WHILE IGAP>1
IGAP=IGAP/2 'shell
' IGAP=IGAP/1.3 'comb
IMAX=N-IGAP
DO
IEX=0
FOR I=1 TO IMAX
IPULUSG=I+IGAP
IF X(I)<=X(IPULUSG) THEN
W=X(I) : X(I)=X(IPULUSG) : X(IPULUSG)=W
IEX=1
END IF
NEXT
LOOP WHILE IEX=1 'shell
' LOOP WHILE IGAP=1 AND IEX=1 'comb
LOOP
END SUB
※REM文２箇所を入れ替えるとコムソート。
＞③．単純挿入法はバイナリサーチで挿入ポイントを決めると早い。
交換回数は単純挿入法と等しいから、手間をかけた割には速くならない
というのが通常の評価です。
また、シェカー法というのは輪をかけてとんでもない方法で、反面教師としてしか使えません。
シェル法以上に複雑なプログラムですが、単純挿入法にすら勝てないから。
＞シェル法のギャップのとり方
1,4,13,....M,3M+1 の他に、
1,3,7,15...M,2M+1 とか、（これもクヌース大先生おすすめ）
IGAP=IGAP*0.45 ※最後はIGAP=1を実行するのをお忘れなく。
というのもおすすめ品。
＞いろんなロジックを教えてください。
単純挿入法ベースのコムソート（コムソートの性格上、最後の仕上げがバブルでないだけ。）
IGAP=N
WHILE IGAP > 2
IGAP = IGAP *10 \ 13
FOR i = IGAP + 1 TO N
J = i - IGAP
IF Key(i) < Key(j) THEN
W=Key(i) : Key(i) = Key(j) :Key(j)= W
End If
NEXT
WEND
For i=2 to N
X=Key(i) : Key(0)=X
j=i-1
While X<Key(j)
Key(j+1)=Key(j): j=j-1
Wend
Key(j+1)=X
Next
マティさん 09月24日
＞クイック派に転向
そう単純に割りきれないところがあります。だからヒープ派というのが厳然として存在。
（私はシェル派なんだけどね。）
クイックソートには欠点があり、
X=Key((L+R)\2)
とした場合、元データがたとえばこういう場合にボロボロになります。
＜1 3 5 7 9 10 8 6 4 2 ＞ （両端に小さい数、真ん中に大きい数。）
最悪時にはスタックオーバーで自爆。自爆しないためには、08月27日の私の記述の改１。
ただし、これだけでは、ｎ^2の時間がかかってしまうので、解除（厳密な解除ではない）には改３が必要。
>バブルソートの進化系はコムソート
バブルソートの最終進化系はクイックで間違いありません。
コムソートは、単純挿入法改もアリ。そして、バブルソート改より速い筈。（キーの長さが短かいならば。）
なお、個人の趣味（＝美意識）になってしまうけど、
omasuさんのように、
'単純挿入法
For i=1 To E
For j=i To 1 Step -1
If KeyTable(j)<KeyTable(j-1) Then
Swap KeyTable(j),KeyTable(j-1)
Else
Exit For
EndIf
Next j
Next i
というのは組む気ナシです。
単純挿入法は、あくまで、
For i=2 to N
X=Key(i) : Key(0)=X
j=i-1
While X<Key(j)
Key(j+1)=Key(j): j=j-1
Wend
Key(j+1)=X
Next
であって、Exit Forのようなムナくそ悪い「例外処理命令」は使いたくないです。
Zgockさん 09月29日
＞２回に分割する場合、バケツソート（注：度数ソート）に比べて速度は２倍、ワークは１００分の１
速度は１／２です。
＞クイックソートは速いアルゴリズムで非常に美しいですが、
＞安定じゃないのだけが欠点ですね。
＞そういう理由からヒープソートをよく使います。
これって、「ヒープソートは安定である」という意味にしか解釈できないのですが。
でも、ヒープソートって安定なんか？
平成１５年度ソフトウェア開発技術者試験午前問13では、「ヒープソートは安定ではない」
が正解なんですけど。
http://sinzo.web.infoseek.co.jp/joho/so ... 03_01.html
クイックソートは、「n^2の時間がかかる数列が存在する」
というのが最大の欠点でしょ？