クイックソートと２分探索

[マサキ]

こんにちわ。
今回は

・＜電話番号ファイル＞からキー（氏名の読み）とデータ（漢字またはカタカナ氏名と電話番号）を読み込む
・これらのデータを配列に格納する。
・クイックソートを持ちいて、辞書式順序になるように並び替える。
・標準入力から、名前の読みを入力させ、これに対応する名前と電話番号を表示させる（2分探索を用いて探索）

というプログラムを作っているのですが、うまく作動しません。
コンパイルはできるのですが、何も出力されないで終わってしまいます。
どのようにすればいいでしょうか？
アドバイスお願いします。

（注）電話番号ファイルは以下のものを使うものとします。


＜電話番号ファイル＞
tanaka 田中 5801
iwasaki 岩崎 5803
akiyama 秋山 5805
takahashi.s 高橋（貞） 5807
ueda 上田 5809
masuda 増田 5811
horio 堀尾 5813
watanabe 渡部 5817
idogawa 井戸川 5153
kasahara 笠原 5154
hori 堀 5162
aiba 相場 5166
wakaki 若木 5158
moen モエン 5160
takahashi.m 高橋（正） 5815
miyoshi 三好 5816
hirata 平田 5173
yamamoto 山本 5175
nakano 中野 5177
kawamo 川面 5179
sato 佐藤 5181
komeda 米田 5183
miyagi 宮城 5185
koyama 小山 5187
kawakami 川上 5189
abe 阿部 5164
kojo 古城 5169
okamura 岡村 5161
matsushita 松下 5821
mizuguchi 水口 5823
kuwata 桑田 5825
tsutsumi 堤 5827
sone 曽根 5829
miura 三浦 5831
kosaka 小坂 5833
itai 衣袋 5835
shinozaki 篠崎 5837
nakaguchi 中口 5156
ohkouchi 大河内 5165

[box]

quicksort関数の

> ind = strcmp(x,a[y].yomi);
> ind2=strcmp(x,a[z].yomi);
> while(ind<0) y=y+1;
> while(ind2>0) z=z-1;

ここのロジックに問題があります。

例えば、１行目を実行してindが負だったとします。
すると、３行目のwhileループを実行し続け、抜け出すことができません。

１行目を実行してindがゼロ以上だったとしても、
２行目でind2が正だったら、４行目のwhileループを実行し続けます。

何も出力しないのは、このように無限ループに陥っているためです。


ところで、今回はquicksort関数を自作することもテーマになっているのでしょうか？
もし、そうでないとすれば、標準関数のqsort()を使えばよいと思います。

[マサキ]

boxさん、ありがとうございます。

> ind = strcmp(x,a[y].yomi);
> ind2=strcmp(x,a[z].yomi);
> while(ind<0) y=y+1;
> while(ind2>0) z=z-1;

を以下のように修正した所、ちゃんと動くようになりました。

while(strcmp(x,a[y].yomi)<0) y=y+1;
while(strcmp(x,a[z].yomi)>0) z=z-1;


しかし、新たな問題が問題が発生しました。
どんな文字を入力しても、全て未登録として認識されてしまいます。
これはやはり、2分探索関数を間違えているということでしょうか？

また、クイックソート関数も自作しなければいけないんです.....
クイックソートのアルゴリズムを習ったので、それに習ってプログラムを作れ。みたいな感じなので......

[box]

> どんな文字を入力しても、全て未登録として認識されてしまいます。

探すことができる名前もあります。例えばmiuraさんのように。

> これはやはり、2分探索関数を間違えているということでしょうか？

二分探索ができるのは、探索対象がソート済みであることが前提ですね。
quicksort()の実行直後に、配列のすべての内容を出力してみてください。
ソートしていないことがわかります。

quicksort()のロジックを見直してください。

ところで、quicksort()の第３引数jは、SIZE-1固定でよいのでしょうか？
ファイルから実際に読んだ件数にする必要はありませんか？
また、並べ替えを行なっているところのコードでは
降順ソートをしているように見えます。
そうすると、search()のロジックと食い違ってこないですか？

[マサキ]

> ところで、quicksort()の第３引数jは、SIZE-1固定でよいのでしょうか？
> ファイルから実際に読んだ件数にする必要はありませんか？

その通りですね。すいません。
読み込むたびにカウンタを増やしていたkを第３引数にすることに修正します。

たしかにクイックソート関数実行後に配列の内容を表示させると、何ともいえない中途半端な順序で表示されました。
入れ替えが行われたり、行われていなかったりしてるようです。
また、どうやら降順に並べ替えられてるような気がします。
しかし私は
基準値よりも大きい値を持つ配列の場所を見つけるために
while(strcmp(x,a[y].yomi)<0) y=y+1;

基準値よりも小さい値を持つ配列の場所を見つけるために
while(strcmp(x,a[z].yomi)>0) z=z-1;

として、これらを入れ替えるために
B[0]=a[y];
a[y]=a[z];
a[z]=B[0];
としたのですが、どうしてこれが降順になってしまうのでしょうか.....??

[マサキ]

すいません。どうやらstrcmp関数の引数が逆だったようです。

//配列の先頭から、文字を比べていく//
while(strcmp(a[y].yomi,x)<0) y=y+1;

//配列の末尾から、文字を比べていく//
while(strcmp(a[z].yomi,x)>0) z=z-1;

このように修正した所、昇順に並べ替えられてるのですが、まだ中途半端に入れ替えが行われていない場所があるようです.......
見直してみたところ、何でこのようになるのかわかりません。何処がおかしいのでしょうか？