文字列ソート

[☆]

いつも、お世話になっています。
本日もよろしくおねがいします。

問題：
ユーザに入力されるa~zまでの文字を含む文字列をアルファベット順に並べ替えるプログラムを作成せよ．

っというものです。

実行例：
kjgdruosdshnkl
ddghjkklnorssu

です。

私が作ったプログラムは、こんな感じです。
すっごく頑張りました＾＾；

#include <stdio.h>
#include <string.h>
#define n 8

void s_quick_sort(char *ss[/url],int top,int end){
  char *key,*wk;
  int i,j;

  key=ss[(top+end)/2];
  i=top-1;
  j=end+1;
  while(1){
    while(strcmp(ss[++i],key)<0);
    while(strcmp(ss[--j],key)>0);
	  if(i>=j)
	  break;
	  wk=ss;
	  ss=ss[j];
	  ss[j]=wk;
	  }
    if(top<i-1)
      s_quick_sort(ss,top,i-1);/*左半分をクイックソート*/
    if(j+1<end)
      s_quick_sort(ss,j+1,end);/*右半分をクイックソート*/
  }

  int main(void){
    int i;
    char st[n][10]=("eee","bbb","ggg","fff","hhh","ccc","aaa","ddd");
    char *p[n];

    for(i=0;i<n;i++){
      p=st;
    }

      s_quick_sort(p,0,n-1);
      for(i=0;i<n;i++){
	printf("%s",p);
      }
	return 0;
    }

ちょっと、というかだいぶ違うのかなぁー。。
どーすればいいでしょうか??
教えてください。

[管理人]

こんにちは。頑張っていらっしゃいますね。

とりあえずぱっと見おかしいのが

char st[n][10]=("eee","bbb","ggg","fff","hhh","ccc","aaa","ddd");

ここで
正しくは

char st[n][10]={"eee","bbb","ggg","fff","hhh","ccc","aaa","ddd"};

です。

字下げが少しおかしいみたいですけど、エディタ何をお使いですか？
タブインデントを使うと綺麗にそろいますよ。

どこで躓いていらっしゃいますか？

[管理人]

２次元配列を使う必要ありませんよね？

答えを書いてしまうとこうなると思います。

#include <stdio.h>
#include <string.h>
#define n 256

void change(int i,int j, char x[ ]){//配列要素i番目とj番目の値を入れ替える
	char t;
	t=x , x=x[j] , x[j]=t;
}

void sort(int l, int r, char x[ ]){//lを一番左端の配列要素、rを一番右端の要素としてソートする。
	int i,j;
	char p;

	i=l;j=r;
	p=x[(l+r)/2];//ピボットの決定

	while(1) {
		while(x<p)//左からピボット以上を探索
			i++;
		while(p<x[j])//右からピボット以下を探索
			j--;
		if(i>=j)//探索地点がぶつかったら終了
			break;
             
        change(i,j,x);//お互い発見した値をいれかえる
		i++;
		j--;
	}
	if(l<i-1)//左範囲が分割可能なら
		sort(l,i-1,x);//左範囲を分割してソートを行う
	if(j+1<r)//右範囲が分割可能なら
		sort(j+1,r,x);//右範囲を分割してソートを行う
}

int main(void){
	char p[n];

	scanf("%s",p);

	sort(0,strlen(p)-1,p);

	printf("%s",p);

	return 0;
}

http://dixq.net/sort.html

ここで紹介しているソースをそのまま使いました。

文字列の最後には\0がはいっていて、これはソートしてしまってはいけないので

strlenで取得した数字-1を渡しています。

どこか解らなかったら聞いてください。

[box]

> 文字列の最後には\0がはいっていて、これはソートしてしまってはいけないので
>
> strlenで取得した数字-1を渡しています。

strlen関数で取得する文字列長には、もともと終端の'\0'の分を含みません。
'\0'を含めてソートしてはいけないから-1した数値を渡しているのではなく、
長さnの文字列の場合、[0]～[n-1]の要素に値が入っているから
sort関数の第1引数が0、第2引数がn-1なのです。
sort関数のコメントに
「lを一番左端の配列要素、rを一番右端の要素としてソートする。」と
書いているとおりです。

[☆]

素早い、返事ありがとうございます。

本当に頑張りました（笑）
お褒めのことば、ありがとうございます。

えっと。。。パソコンにLINUXが入ってるんで、自分で、打ってるんですけど・・・
見にくかったですよね??
見やすい、プログラミングの書きかたって難しいです＞＜

boxさんも、ありがとうございます。
今から、頑張って理解します。
また、質問にきます。
そのときは、また、よろしくおねがいします。

[フリオ]

　
　この場合は、
英文字それぞれの数を数えてその数づつアルファベット順に表示すればいい
ので、クィックソートを使うまでも無いです。

#include <stdio.h>
#include <ctype.h>

int main(void)
{
	char *chars = "abcdefghijklmnopqrstuvwxyz";
	int c, c_count[256] = {0,};
	
	while((c = getchar()) != '\n') c_count[tolower(c)] ++;
	for( ; *chars != '\0'; chars ++){
		for( ; c_count[*chars] > 0; c_count[*chars] --){
			putchar(*chars);
		}
	}
	return 0;
}

　

[管理人]

boxさんのおっしゃるとおりです・・(_ _||)

[管理人]

＞えっと。。。パソコンにLINUXが入ってるんで、自分で、打ってるんですけど・・・


OSはWindowsとリナックスしか使ったこと無いのでよくわかりませんけど、
プログラムを書くエディタならタブキーを押すと大抵インデントされると思いますけど、
どうでしょう？

[☆]

そーなんですかぁ??
一応、tabでもきれいには、なるんですけどねぇ。。。


そんな簡単な方法もあるんですねぇー!!!!
びっくりです。

[管理人]

フリオさん、そんな方法があるとは・・。
簡単ですね。
ホントプログラムは考えようでどうとにもなりますねぇ。

[☆]

えっと。。。もう一個、問題なんですが・・・・
「ユーザによって数値が入力されるたびに，それまで入力された全ての数値を昇順にソートして表示するプログラムを作成せよ．」

っていう、教科書の問題なんですが、これは、「再帰的クイックソート」とかそういうものなんですか??

[box]

> っていう、教科書の問題なんですが、これは、「再帰的クイックソート」とかそういうものなんですか??

ソートのアルゴリズムは何種類もあります。
必ずクイックソートを使わねばならない、というわけではありません。

なお、クイックソートのアルゴリズムはもともと再帰的であるため、
「再帰的クイックソート」という言い方は通常しません。

「数値が入力されるたびに」とのことですが、入力する個数の上限は決まっていますか？
個数の上限（例えば10個）が決まっていれば、その分の配列を定義しておいて
・配列の各要素に入力する
・入力終了後、配列の要素をソートする
というプログラムを書くことになります。

個数の上限が決まっていなければ、配列を直接定義することはできません。
もしかすると100個の数値を入力するかもしれないのに、[10]という配列では
足りないからです。
この場合は、別の考え方が必要です。

[☆]

上限はきまっていません。

999が入力されたら、終了するものなんですが・・・
この場合は、どうすればいいんでしょうか??

[box]

> 上限はきまっていません。
>
> 999が入力されたら、終了するものなんですが・・・

ということは、999という入力終了の合図があるまでは、
千個でも二千個でも（あるいは、もっとたくさん）入力する可能性がある、
ということですね。

このような場合、パッと思いつくのは「リスト構造」を使った実装です。
「リスト構造」や「自己参照型構造体」という言葉を聞かれたことはありますか？

[☆]

そうですね★
999が押されるまで、ずっとプログラムが働きますよね。

＞「リスト構造」や「自己参照型構造体」という言葉を聞かれたことはありますか？
いいえ。。まったく聞いたことありません＾＾；
教えてもらえますか???

[box]

リスト構造を理解するには、ポインタの知識が欠かせません。
ポインタについてある程度ご存じであるという前提で話を進めてよろしいですか？

もし、ポインタのことをあまりご存じでないとすると、
リスト構造よりも先に、ポインタについて勉強していただかねばなりません。

[☆]

はい★ポインタは、もう学習済みです。
おねがいします。

[☆]

えっと、調べて、自分なりに作って見ました★＾＾；

こんな感じです↓↓

#include<stdio.h>

struct node
{
int value;
struct node *next;
struct node *prev;
};

struct node head;

int main(void)
{
struct node *new, *p;
int n;

head.next = NULL;
head.prev = NULL;

while(1){

printf("数字を入力せよ(999で終了)");
scanf( "%d", &n);

if(n != 999){
new = (struct node*)malloc( sizeof( struct node ) );
if( new == NULL ){
printf( "error\n" );
return 1;
}

new -> value = n;
new -> prev = &head;
new -> next = head.next;
if (new -> next != NULL)
head.next -> prev = new;
head.next = new;
for(p = head.next; p != NULL; p = p -> next)
printf("%d ", p->value);
printf("\n");
}
else break;
}
return 0;

}

でも。。。実行結果が。。
数字を入力せよ(999で終了)24
24
数字を入力せよ(999で終了)15
15 24
数字を入力せよ(999で終了)28
28 15 24
数字を入力せよ(999で終了)11
11 28 15 24
数字を入力せよ(999で終了)999

おかしいんです。。
3回目からおかしいです。。
どこがダメなんでしょうか???

[box]

> えっと、調べて、自分なりに作って見ました★＾＾；

ありがとうございます。
調べていただけて助かります。

> struct node
> {
> int value;
> struct node *next;
> struct node *prev;
> };

構造体の定義についてですが、今回の問題では「前のデータへのポインタ」
つまりprevメンバーを特に持たなくてもよいかもしれません。
もちろん、リスト構造を逆順にたどる必要が将来出てくることを見越してのことならば、
prevメンバーを持っておく必要があります。

> でも。。。実行結果が。。

実行結果をよくごらんになってください。
3回目からおかしいというより、入力したのとは逆の順番に
表示していることがおわかりになると思います。

つまり、今のプログラムでは、最初に入力した24を最後に表示し、
最後に入力した11を最初に表示するようになっています。
理由は、リスト構造にデータを挿入する際、今は必ず先頭に
挿入するようになっているためです。ここを、
「リスト構造を順に見ていき、現在着目している場所に格納している
データが、今回挿入しようとしているデータより小さければ、
現在着目している場所の次に挿入する」という風に
修正すればよいはずです。

[☆]

なるほど!!!

forの二重ループとか使うんでしょうか??

[管理人]

たんにこんなんじゃダメなんでしょうか＾＾；

#include <stdio.h>
#include <string.h>
#define N 256

void change(int i,int j, int x[ ]){//配列要素i番目とj番目の値を入れ替える
	int t;
	t=x , x=x[j] , x[j]=t;
}

void sort(int l, int r, int x[ ]){//lを一番左端の配列要素、rを一番右端の要素としてソートする。
	int i,j, p;

	i=l;j=r;
	p=x[(l+r)/2];//ピボットの決定

	while(1) {
		while(x<p)//左からピボット以上を探索
			i++;
		while(p<x[j])//右からピボット以下を探索
			j--;
		if(i>=j)//探索地点がぶつかったら終了
			break;
             
        change(i,j,x);//お互い発見した値をいれかえる
		i++;
		j--;
	}
	if(l<i-1)//左範囲が分割可能なら
		sort(l,i-1,x);//左範囲を分割してソートを行う
	if(j+1<r)//右範囲が分割可能なら
		sort(j+1,r,x);//右範囲を分割してソートを行う
}

void disp(int num,int p[/url]){
	printf("現在のソート結果　");
	for(int i=0;i<=num;i++)
		printf("%d ",p);
	printf("\n");
}

int main(void){
	int num=0,p[N];

	while(1){
		printf("Input ---> ");
		if(scanf("%d",&p[num]) == EOF) break;
		if(num>1) sort(0,num,p);
		disp(num,p);
		num++;
	}
	return 0;
}

　　

[管理人]

char t;
になってました(_ _||)

int t;
に上記直しておきました。
さっきのだと256以上の数字を入力したらおかしくなってたはず。
やりたいことはこういうのとは違うんですか？

[box]

> たんにこんなんじゃダメなんでしょうか＾＾；

要素数の上限が決まっていれば、全く問題ありません。
ただ、配列を用いている限り、その配列の要素数を超える
入力ができないことはご存じのとおりです。

教科書に載っている「ユーザによって数値が入力されるたびに，
それまで入力された全ての数値を昇順にソートして表示する
プログラムを作成せよ．」という今回の問題で、
「入力する数値は最大256個とする」などの但書があれば、
リスト構造など持ち出すまでもないですが…。

[Yuki]

realloc関数と、入力数を保持する変数を利用すれば、リスト構造に
しなくてもいけるのではないでしょうか。

[box]

> forの二重ループとか使うんでしょうか??

わかりやすそうなやり方は、
・for文やwhile文を使って、リスト構造の中を先頭から走査する
・走査中、現在着目している場所にあるデータと、
　今回挿入しようと思っているデータの大小関係を比較する（もちろんif文で）
・前項での比較結果により、データを挿入すべき場所がわかる
・データの挿入に伴うポインタの付け替えを適切に行ない、
　リスト構造中のデータがソートされた状態にする

データの挿入に伴うポインタ付け替えのイメージは下図のとおりです。
線がずれている箇所はご容赦ください。

【挿入前】

 着目中の
 データ
+--------+                        +--------+
|  next  | ---------------------> |  next  |
+--------+                        +--------+
| データ |                        | データ |
+--------+        挿入する        +--------+
                  データ
                 +--------+
                 |  next  |
                 +--------+
                 | データ |
                 +--------+


【挿入後】

 着目中の
 データ
+--------+                        +--------+
|  next  | --+                +-> |  next  |
+--------+   |                |   +--------+
| データ |   |                |   | データ |
+--------+   |    挿入する    |   +--------+
             |    データ      |
             |   +--------+   |
             +-> |  next  | --+
                 +--------+
                 | データ |
                 +--------+

[GPGA]

> realloc関数と、入力数を保持する変数を利用すれば、リスト構造に
> しなくてもいけるのではないでしょうか。
VectorにするかListにするかの差ですね。
両方作ると勉強になると思います。

効率で考えるならば、Vectorの場合コピーを行う必要があるため
数が多くなるほど、重くなってしまうのでリストのほうがよいと思います。

[box]

> realloc関数と、入力数を保持する変数を利用すれば、リスト構造に
> しなくてもいけるのではないでしょうか。

おっしゃるとおりです。
１個数値を入力するごとに、その時点での総個数分の領域をreallocして、
領域内の数値群をソート済の状態にしておけば、何もリスト構造にこだわる
必要はないですね。

＞☆さん
よけいな手間を取らせてしまって、すみません。
まあ、今回はリスト構造の練習問題だと思って、
時間があれば取り組んでみてください。

[管理人]

#include <stdio.h>
#include <memory.h>
#include <stdlib.h>

void change(int i,int j, int x[ ]){//配列要素i番目とj番目の値を入れ替える
	int t;
	t=x , x=x[j] , x[j]=t;
}

void sort(int l, int r, int x[ ]){//lを一番左端の配列要素、rを一番右端の要素としてソートする。
	int i,j, p;

	i=l;j=r;
	p=x[(l+r)/2];//ピボットの決定

	while(1) {
		while(x<p)//左からピボット以上を探索
			i++;
		while(p<x[j])//右からピボット以下を探索
			j--;
		if(i>=j)//探索地点がぶつかったら終了
			break;
             
        change(i,j,x);//お互い発見した値をいれかえる
		i++;
		j--;
	}
	if(l<i-1)//左範囲が分割可能なら
		sort(l,i-1,x);//左範囲を分割してソートを行う
	if(j+1<r)//右範囲が分割可能なら
		sort(j+1,r,x);//右範囲を分割してソートを行う
}

void disp(int num,int p[/url]){
	printf("現在のソート結果　");
	for(int i=0;i<=num;i++)
		printf("%d ",p);
	printf("\n");
}

int main(void){
	int num=0,*p,*pp;

	p = (int *)malloc(sizeof(int)*(num+1));

	while(1){
		printf("Input ---> ");
		if(scanf("%d",&p[num]) == EOF)
			break;
		else{
			pp = (int *)malloc(sizeof(int)*(num+1));
			memcpy(pp, p, sizeof(int) * (num+1));
			free(p);
			p = (int *)malloc(sizeof(int)*(num+2));
			memcpy(p, pp, sizeof(int) * (num+1));
			free(pp);
		}

		if(num>1) sort(0,num,p);
		disp(num,p);
		num++;
	}
	free(p);
	return 0;
}

こんな感じでいいような・・。

確かに毎回フリー、確保、コピーが無駄ですね。

[管理人]

☆さんへ、
一応私の書いたコードでよければ説明します。
ホントはもっと綺麗な書き方があるんでしょうけど、先ほど作ったコードを利用した方法では私にはこれしか思いつかないので。

まず、本当にソートに使用するpという配列を用意するため、
int *p;
でポインタを宣言します。
mallocでこのpに領域を確保させます。
まず最初は
int型の領域1つ分でいいので、

p = (int *)malloc(sizeof(int)*(num+1));

のnumが0ですからint型の領域一つ分つまりsizeof(int)*(num+1)だけpに確保します。

if(scanf("%d",&p[num]) == EOF) break;

ここは入力を受ける部分で、入力がEOFならループを抜けます。

EOFは入力中に　ctrl + Z を押すとEOFとなります(環境によってはＤとか)。

elseで行われる処理は終わらず継続するときの処理で、

まず、pの内容をppにコピーします。

これはpにもう一つ大きな領域を確保させるためであり、pはあらたに確保させるとき、freeで消えてしまうため、コピーをとっておかないといけないためです。

ppの領域をpと同じだけ確保し、

pp = (int *)malloc(sizeof(int)*(num+1));

pの内容をppにコピーします。

memcpy(pp, p, sizeof(int) * (num+1));

pを解放します。

free(p);

pに先ほどより１つ多い領域を確保させます。

p = (int *)malloc(sizeof(int)*(num+2));

pにppの内容をコピーします。

memcpy(p, pp, sizeof(int) * (num+1));

ppを解放します。

free(pp);

あとは、２回目のループからソートを行い、表示しているだけです。

どこかわからないところや、コードに不審な点があれば伝えてください。

[☆]

みなさん、どぉーも、ありがとーございます。。。

一応今回は、ソートの練習問題だったので、リスト構造のやりかたの練習をしてみます。

[管理人]

そういえばソートして表示って問題の言葉に捉われなければ、単純に比較してコピーするだけの方がずっと計算早いですね。

結局リストと同じことになりそうですけど。
リストの配列版というか

#include <stdio.h>
#include <memory.h>
#include <stdlib.h>

void disp(int num,int p[/url]){
	for(int i=0;i<=num;i++)
		printf("%d ",p);
	printf("\n");
}

int main(void){
	int i,j,num=0,*p,*pp,x;
	p = (int *)malloc(sizeof(int)*(num+1));
	while(1){
		printf("Input ---> ");
		if(scanf("%d",&x) == EOF)
			break;
		else {
			pp = (int *)malloc(sizeof(int)*(num+1));
			memcpy(pp, p, sizeof(int) * (num+1));
			free(p);
			p = (int *)malloc(sizeof(int)*(num+2));
			memcpy(p, pp, sizeof(int) * (num+1));
			free(pp);
		}
		if(num>0){
			for(i=0;i<num;i++)
				if(p>x) break;
			for(j=num;j>=i;j--)
				p[j+1]=p[j];
			p=x;	
		}
		else
			p[0]=x;
		disp(num,p);
		num++;
	}
	free(p);
	return 0;
}

　　

[管理人]

↑クリックで画像が拡大↑

ちょっと手元にパワーポイントとか絵を書いて説明できるものがないんで、
手書きの写真で説明します…；

汚い字ですみませんm(_ _)m

これは

8 11 13 21

と並んでいるときに

12が入力されたときに、どういう風に割り込んで、並べているか説明したものです。

[管理人]

う、みなさんのお話を見ずに投稿しているとreallocのお話が・・。
reallocは使ったこと無かったので思いつきませんでした。
mallocよりreallocを使った方がずっとスマートですね(_ _|||)

[管理人]

#include <stdio.h>
#include <stdlib.h>

void disp(int num,int p[/url]){
	for(int i=0;i<=num;i++)
		printf("%d ",p);
	printf("\n");
}

void sort(int *p,int num,int x){
	int i,j;
	for(i=0;i<num;i++) if(p>x) break;
	for(j=num;j>=i;j--)	p[j+1]=p[j];
	p=x;
	return ;
}

int main(void){
	int i,j,num=0,*p,x;
	p = (int *)malloc(sizeof(int)*(num+1));
	while(1){
		printf("Input ---> ");
		if(scanf("%d",&x) == EOF) break;
		else p=(int *)realloc(p,sizeof(int)*(num+2));
		if(num>0) sort(p,num,x);
		else p[0]=x;
		disp(num,p);
		num++;
	}
	free(p);
	return 0;
}

reallocを使って書き直しました。
何度もすみません(_ _||)

[☆]

すごいですね。
わざわざ手書きまでしていただいて、すみません。
typedefを使えば、sortを何回もかかなくて、すむんですよね★
この前、教えていただきました!!

[管理人]

どのソートが早いか測定してみました。
新しいトピをたてたのでよければみてください。

[☆]

はい★ありがとうございます。

あと、もう一つ質問です。いいですか??

管理人さんに教えていただいたプログラムを、「999という数字が入力されたら、終了」という風にしたいんですけど、どのようにやればいいんしょうか??
どこに、その条件をいれるのかがわかりません。

お願いします。

[管理人]

if(scanf("%d",&x) == EOF) break;
ここの部分でループを抜けています。

入力がEOFならブレイクという意味です。
これを入力されたものが999ならブレイクにすればいいのです。
つまり、スキャンしてから、その値がつまりxが999ならブレイクです。

[☆]

if(scanf("%d",&x)==999) break;

でいいですか??

[☆]

できましたぁーーーー★

ありがとうございます★