文字列ソート

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら

文字列ソート

#1

投稿記事 by » 11年前

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

問題:
ユーザに入力される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;
    }


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

管理人

Re:文字列ソート

#2

投稿記事 by 管理人 » 11年前

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

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

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

ここで
正しくは

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

です。

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

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

管理人

Re:文字列ソート

#3

投稿記事 by 管理人 » 11年前

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

答えを書いてしまうとこうなると思います。
#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

Re:文字列ソート

#4

投稿記事 by box » 11年前

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

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

Re:文字列ソート

#5

投稿記事 by » 11年前

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

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

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

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

フリオ

Re:文字列ソート

#6

投稿記事 by フリオ » 11年前

 
 この場合は、
英文字それぞれの数を数えてその数づつアルファベット順に表示すればいい
ので、クィックソートを使うまでも無いです。
#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;
}
 

管理人

Re:文字列ソート

#7

投稿記事 by 管理人 » 11年前

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

管理人

Re:文字列ソート

#8

投稿記事 by 管理人 » 11年前

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


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

Re:文字列ソート

#9

投稿記事 by » 11年前

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


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

管理人

Re:文字列ソート

#10

投稿記事 by 管理人 » 11年前

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

Re:文字列ソート

#11

投稿記事 by » 11年前

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

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

box

Re:文字列ソート

#12

投稿記事 by box » 11年前

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

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

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

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

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

Re:文字列ソート

#13

投稿記事 by » 11年前

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

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

box

Re:文字列ソート

#14

投稿記事 by box » 11年前

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

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

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

Re:文字列ソート

#15

投稿記事 by » 11年前

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

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

box

Re:文字列ソート

#16

投稿記事 by box » 11年前

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

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

Re:文字列ソート

#17

投稿記事 by » 11年前

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

Re:文字列ソート

#18

投稿記事 by » 11年前

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

こんな感じです↓↓

#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

Re:文字列ソート

#19

投稿記事 by box » 11年前

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

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

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

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

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

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

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

Re:文字列ソート

#20

投稿記事 by » 11年前

なるほど!!!

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

管理人

Re:文字列ソート

#21

投稿記事 by 管理人 » 11年前

たんにこんなんじゃダメなんでしょうか^^;
#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;
}


  

管理人

Re:文字列ソート

#22

投稿記事 by 管理人 » 11年前

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

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

box

Re:文字列ソート

#23

投稿記事 by box » 11年前

> たんにこんなんじゃダメなんでしょうか^^;

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

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

Yuki

Re:文字列ソート

#24

投稿記事 by Yuki » 11年前

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

box

Re:文字列ソート

#25

投稿記事 by box » 11年前

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

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

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

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


【挿入後】

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

GPGA

Re:文字列ソート

#26

投稿記事 by GPGA » 11年前

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

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

box

Re:文字列ソート

#27

投稿記事 by box » 11年前

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

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

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

管理人

Re:文字列ソート

#28

投稿記事 by 管理人 » 11年前

#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;
}



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

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

管理人

Re:文字列ソート

#29

投稿記事 by 管理人 » 11年前

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

まず、本当にソートに使用する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となります(環境によってはDとか)。

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に先ほどより1つ多い領域を確保させます。

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

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

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

ppを解放します。

free(pp);

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

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

Re:文字列ソート

#30

投稿記事 by » 11年前

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

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

閉鎖

“C言語何でも質問掲示板” へ戻る