クイックソート

質問

名前と年齢を入力したあとに、1人の名前を入力して2分探索で探索する
プログラムを書いたのですが、これにクイックソート法の整列手続き（辞書式順序）を加えたいのですが、どこに何を加えたら動くのか教えていただけないでしょうか。

まだプログラムを習い始めたばかりでプログラム自体も、字下げもろくにできてませんが、どうかよろしくお願いします。

#include<stdio.h>
#include<string.h>
#include<conio.h>

struct record{
char key[20]
int dat;
};

struct record A[100];
int n=0;

void insert(char x[],int y){
n++;
strcpy(A[n].key,x);
A[n].dat=y;
}

int binarysearch(char target[],int *pos){
int top,bottom,found,pt;
top=n;
bottom=1;
found=0;

while(top>=bottom&&!found){
pt=(top+bottom)/2;
if(strcmp(A[pt].key,target)>0)
top=pt-1;
else if (strcmp(A[pt].key,target)<0)
bottom=pt+1;
else
found=1;
}
*pos=pt;
return found;
}

int main(void){
char name[100],sname[100];
int old,ptr;
scanf("%s",name);

while(strcmp(name,"0")){
scanf("%d",&old);
insert(name,old);
scanf("%s",name);
}

printf("指定する名前を入力してください\n");
scanf("%s",name);

if(binarysearch(sname,&ptr)){
printf("%s %d\n",A[ptr].key,A[ptr].dat);
}
else
printf("いません。\n");

getch();
return0;
}

回答No.5

JaritenCat · ベストアンサー

qsort関数を使うのであればこんな感じ？(全角空白文字を半角にしてください)
qsort用の比較関数を追加して、Aの添え字をn=0から使うように変更しています。。
#include <stdio.h>
#include <string.h>
#include <stdlib.h> /* qsort */

struct record{
　char key[20];
　int dat;
};

struct record A[100];
int n=0;

void insert(char x[],int y) {
　strcpy(A[n].key,x);
　A[n].dat=y;
　n++; /* n=0から使うので登録後にインクリメント */
}

int binarysearch(char target[],int *pos) {
　int top,bottom,found,pt;
　top=n-1;　/* 登録の最大はA[n-1] */
　bottom=0; /* 登録の最小はA[0] */
　found=0;　/* 見つかったら1 */

　while (top>=bottom&&!found) {
　　pt=(top+bottom)/2;
　　if (strcmp(A[pt].key,target)>0) {
　　　top=pt-1;
　　} else if (strcmp(A[pt].key,target)<0) {
　　　bottom=pt+1;
　　} else {
　　　found=1;
　　}
　}
　*pos=pt;
　return found;
}

/* qsort用比較関数 */
int reccmp(const void *a, const void *b) {
　struct record *aa = (struct record *)a; /* 型をあわせる */
　struct record *bb = (struct record *)b; /* 型をあわせる */
　return strcmp(aa->key, bb->key);
}

int main(void){
　char name[100],sname[100];
　int old,ptr;
　int i;
　/* データ入力 */
　scanf("%s",name);
　while(strcmp(name,"0")) {
　　scanf("%d",&old);
　　insert(name,old);
　　scanf("%s",name);
　}
　/* ソート */
　printf("入力データ\n"); for (i=0; i<n; i++) printf("%d %s %d\n",i,A[i].key,A[i].dat);
　qsort(A, n, sizeof(struct record), reccmp);
　printf("ソート\n"); for (i=0; i<n; i++) printf("%d %s %d\n",i,A[i].key,A[i].dat);
　/* 検索入力 */
　printf("指定する名前を入力してください\n");
　scanf("%s",sname);
　/* 検索結果(1個だけ)表示 */
　if (binarysearch(sname,&ptr)) {
　　printf("%s %d\n",A[ptr].key,A[ptr].dat);
　} else {
　　printf("いません。\n");
　}

　return 0;
}

回答No.4

onnobu

「C言語」「アルゴリズム」「クイックソート」などでgoogleで検索してみて下さい。

http://oku.edu.mie-u.ac.jp/~okumura/algo/archive/

などにサンプルのソースコードなどもありました。

回答No.3

noname#75489

C言語のソートアルゴリズムは検索すれば山ほどヒットすると思いますが、ヒントになるような情報は何も見つからなかったのでしょうか？

> まだプログラムを習い始めたばかりで
3ヶ月も前にこれくらいのプログラムが書けるなら、クイックソートぐらい楽勝だと思いますが...

参考URL：

http://okwave.jp/qa3981332.html

回答No.2

aigaion

>どこに何を加えたら動くのか
データの入力が終わった後，事前にソートが必要な処理の前ですよね？
クィックソートを加えたいと言っているのに「何を加えたら」という表現が不可解ですね．
クィックソート関数を挿入するのではないのですか？

>クイックソート法
たぶん，何かの課題だと思います．
それだと自力でクィックソートを書かないと駄目ですので
教科書等を調べて自分で書いてみましょう．
その上でどうすればよいのかわからないという質問をしてください．
この質問は，ここでの禁止事項である「丸投げ」に近い形です．

回答No.1

koko_u_

>プログラムを書いたのですが、これにクイックソート法の整列手続き（辞書式順序）を加えたいのですが、
>どこに何を加えたら動くのか教えていただけないでしょうか。

このプログラムは自分でコーディングしたのですか？
自分で作成したのなら、何処に何を追加しなければならないか分かると思うのですが。