ページ 11

文字のバブルソート

Posted: 2009年11月29日(日) 16:58
by サック
こんにちは。質問なんですが、文字配列を昇順(a,b,c,…順)に並び替えるプログラムをバブルソートとポインタを使って記述しなさい、という問題を学校の宿題でやっています。そこで、以下のようなプログラムを作ってみたんですが、実行して文字を入力しても昇順に並び変えられていなく、そのままの順番で表示されてしまいます。どこを直せば昇順になるか教えてほしいです。
#include<stdio.h>
void sort(char a[/url],int n){
int aa,k,m;
char *pa=a+1;
for(m=n;m>=2;m--){
for(k=1;k<n;k++){
if(*pa>*(pa+2)){
aa=*(pa+2);
*(pa+2)=*pa;
*pa=aa;
a[k]=*pa++;
}
}
}
}
main(){
int n,m;
char a[100];
printf("データ数を入力してください:");
scanf("%d",&n);getchar();
for(m=1;m<=n;m++){
printf("a[%d]=???",m);
scanf("%c",&a[m]);getchar();
}
for(m=1;m<=n;m++){
printf("%c",a[m]);
}
}

Re:文字のバブルソート

Posted: 2009年11月29日(日) 17:30
by やっくん
sort()関数をメイン側で呼び出してないからではないでしょうか?

あと、もしできるならば記事の編集をしてソースコードを
<pre>

</pre>
で挟んでもらっていいでしょうか。
そうしなければインデントされないので見にくくなってしまいます。

Re:文字のバブルソート

Posted: 2009年11月29日(日) 18:24
by サック
やっくんさんコメントありがとうございます。みにくくて申し訳ありません。sort(a,n)を入れてみたのですが、実行結果が以下のようになってしまいます。どうすればよいのでしょうか??
データ数を入力してください:3
a[1]=???f
a[2]=???g
a[3]=???a
フフフPress any key to continue

Re:文字のバブルソート

Posted: 2009年11月29日(日) 18:51
by non
環境ともう一度、プログラムを添付してください。

Re:文字のバブルソート

Posted: 2009年11月29日(日) 19:13
by サック
文字を昇順に並び変えるプログラムで、バブルソートとポインタを使って記述しなさいという問題です。作ったプログラムは以下の通りです。
#include<stdio.h>
void sort(char a[/url],int n){
int aa,k,m;
char *pa=a+1;
for(m=n;m>=2;m--){
for(k=1;k<n;k++){
if(*pa>*(pa+2)){
aa=*(pa+2);
*(pa+2)=*pa;
*pa=aa;
a[k]=*pa++;
}
}
}
}
main(){
int n,m;
char a[100];
printf("データ数を入力してください:");
scanf("%d",&n);getchar();
for(m=1;m<=n;m++){
printf("a[%d]=???",m);
scanf("%c",&a[m]);getchar();
}
sort(a,n);
for(m=1;m<=n;m++){
printf("%c",a[m]);
}
}
これを実行すると、以下のようにまってしまいます。
データ数を入力してください:3
a[1]=???c
a[2]=???b
a[3]=???a
フフフPress any key to continue
コメントお願いします。

Re:文字のバブルソート

Posted: 2009年11月29日(日) 19:21
by Mist
#include<stdio.h>
void sort(char a[/url],int n){
	int aa,k,m;
	char *pa=a+1;
	for(m=n;m>=2;m--){
		for(k=1;k<n;k++){
			if(*pa>*(pa+2)){
				aa=*(pa+2);
				*(pa+2)=*pa;
				*pa=aa;
				a[k]=*pa++;
			}
		}
	}
}
main(){
	int n,m;
	char a[100];
	printf("データ数を入力してください:");
	scanf("%d",&n);getchar();
	for(m=1;m<=n;m++){
		printf("a[%d]=???",m);
		scanf("%c",&a[m]);getchar();
	}
	sort(a,n);
	for(m=1;m<=n;m++){
		printf("%c",a[m]);
	}
}
貼りなおしました。
規約をよく読んで環境かいてください。

Re:文字のバブルソート

Posted: 2009年11月29日(日) 19:32
by サック
環境はwindows,コンパイル名はVC++です。よりしくお願いします

Re:文字のバブルソート

Posted: 2009年11月29日(日) 20:40
by non
サックさんの作ったsort関数とと配列の表記で解いたプログラムを比較できるように
並べて書いてみました。
void sort(char a[/url],int n){ 
	int aa,k,m; 
	char *pa=a+1; 
	for(m=n;m>=2;m--){ 
		for(k=1;k<n;k++){ 
			if(*pa>*(pa+2)){ 
				aa=*(pa+2); 
				*(pa+2)=*pa; 
				*pa=aa; 
				a[k]=*pa++; 
			} 
		} 
	} 
} 
void sort(char a[/url], int n)
{
	int k,m;
	char aa;
	for(m=n;m>=2;m--){ 
		for (k=1 ; k < m; k++) {
			if (a[k] > a[k+1]) {  
				aa = a[k];       
				a[k] = a[k+1];
				a[k+1]= aa;
			}
		}	
	}
}

Re:文字のバブルソート

Posted: 2009年11月29日(日) 23:03
by サック
比較して作ってみましたが実行結果がうまくいきません。
#include<stdio.h>
void sort(char a[/url],int n){
int k,m;
char aa,*p=a+1;
for(m=n;m>=1;m--){
for(k=1;k<m;k++){
if(*p>*(p+1)){
aa=*(p+1);
*(p+1)=*p;
*p=aa;
}
}
}
}
main(){
int n,k;
char a[100];
printf("データ数を入力してください:");
scanf("%d",&n);getchar();
for(k=1;k<=n;k++){
printf("a[%d]=???",k);
scanf("%c",&a[k]);getchar();
}
sort(a,n);
for(k=1;k<=n;k++){
printf("%c",a[k]);
}
}
データ数を入力してください:3
a[1]=???c
a[2]=???b
a[3]=???a
bcaPress any key to continue

Re:文字のバブルソート

Posted: 2009年11月30日(月) 01:14
by やっくん
>サックさん
sort関数でchar型のポインタ*pを宣言してそれを用いて、ソート処理を行っていますが、ポインタpが指しているアドレスが常に同じとなっています。
for(m=n;m>=1;m--){ 
  for(k=1;k<m;k++){ 
    if(*p>*(p+1)){ 
    aa=*(p+1); 
    *(p+1)=*p; 
    *p=aa;
    ++p;
  } 
}
++p;このようにすることで次のアドレス(次の配列の要素と捉えて良いです)を指します。
ですが、↑に書いた通りにしてもきちんと動きません。
バブルソートを少しわかりにくいかもしれませんが図で表すと、
    (要素)
 比較  123456  (比べる順序)
1回目:○○○○○○ 6と5→5と4→4と3→3と2→2と1
2回目:■○○○○○ 6と5→5と4→4と3→3と2 
3回目:■■○○○○ 6と5→5と4→4と3
4回目:■■■○○○ 6と5→5と4
5回目:■■■■○○ 6と5
6回目:■■■■■■ 完成

○が比べて変更する部分で、■は並べ終わった数値です。
(比べる順序)に書いてるように後ろから比べていくことにします。
そうすると、一列比べ終わるごとに一番最初の方から小さい値が入っていきます。
これをポインタを使って表現すると、
まず6番目を指すポインタpをセットします。
一つ前の要素5番目はp-1で表されます。
次に5番目と4番目を見たいのですが、サックさんの書き方ですと、ポインタで指している場所を変えてないため、また6番目と5番目を比較してしまいます。ですのでポインタをずらす必要があります。
1個ずつポインタをずらしていき、2番目と1番目までこの方法で比較した場合、ポインタは2番目を指しているはずです。
そうすると2回目の比較に移行するする際に不都合が起きてしまいます(6番目を比較したいのに2番目を指している)。ですので6番目にポインタを戻してあげる必要があります。
あとはこれの繰り返しで並べ替えることができます。

あと、ソースコードが見にくくなっているのはソースコードを<Pre>~</Pre>で囲んでいないからですよ。

<Pre>
#include<stdio.h>

ー略ー

</Pre>
と記せばきれいにインデントされたままになりますよ。
<>は半角です。