昇順並び替えの出力

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

昇順並び替えの出力

#1

投稿記事 by トワ » 9年前

こんにちは
課題で少し分らないところがあるので助けてほしいです。

入力された10個の整数を昇順に並び替えて出力する。
というものなので

/**************
sort 10 data
***************/

#include <stdio.h>
#define OK 0
#define MAX 10

int inputnum(int num[]);
int outputnum(int num[]);
main(){
int num[MAX];
int status;

printf("学籍番号 名前\n");
status=inputnum(num);
status=sortnum(num);
status=outputnum(num);
return(OK);
}
/**************************
input 10 numbers to array
***************************/
int inputnum(int num[]){
int i;
for(i=0;i<MAX;i++){
printf("数値%d = ",i+1);
scanf("%d",&num);
}
printf("数値入力完了\n");
return(OK);
}
/****************
sort 10 numbers
*****************/
#define FON 1
#define FOFF 0
int sortnum(int num[]){
int i,j;
int work;

for(i=0;i<MAX;i++){
for(j=i+1;j<MAX;j++){
if(num>num[j]){
work=num[j];
num[j]=num;
num=work;
}
}
}
printf("並び替え完了\n");
return (OK);
}
/**************************
output 10 numbers to array
***************************/
int outputnum(int num[]){
int i;
for(i=0;i<MAX;i++){
printf("数値%d = %d\n",i+1,num);
}
printf("数値出力完了\n");
return(OK);
}

赤の部分を自分で作成しました。
(この部分だけ各自作成する課題です)
これでもちゃんと出力できるのですが、ループ(無駄?)が多いと言われました。
どこを直せば無駄なくできるのでしょうか。

また、コンパイル時に「statusに代入した値は使われていない(関数main)」という警告が出ます。
これは解決しなくても動くようですがこれを解決できればした方がいいとのことなのでどうすればよいかわかる方いましたら教えていただきたいです。

よろしくお願いします。

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: 昇順並び替えの出力

#2

投稿記事 by みけCAT » 9年前

トワ さんが書きました:赤の部分を自分で作成しました。
(この部分だけ各自作成する課題です)
他の部分も書き換えていいのですか?
トワ さんが書きました:これでもちゃんと出力できるのですが、ループ(無駄?)が多いと言われました。
どこを直せば無駄なくできるのでしょうか。
これは確かにO(N^2)の遅いアルゴリズムですね。
O(N log N)のアルゴリズムに切り替えるといいかもしれません。
(ただし、今回はNが小さいので、定数倍も考えると本当に改善するかはわかりませんが…)
トワ さんが書きました:また、コンパイル時に「statusに代入した値は使われていない(関数main)」という警告が出ます。
これは解決しなくても動くようですがこれを解決できればした方がいいとのことなのでどうすればよいかわかる方いましたら教えていただきたいです。
他の部分も書き換えていいのなら、単純に変数statusとそれへの無駄な代入を削除すればいいでしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: 昇順並び替えの出力

#3

投稿記事 by みけCAT » 9年前

もしくは、単にソースコードが無駄に長かったり、for文が無駄に多かったりということでしたら、減らせばいいでしょう。
例えば

コード:

int sortnum(int num[]){
	int*x,*y,k,j=MAX-1,i=MAX*j;for(;i--;*x>*(y=x+1)&&(k=*y,*y=*x,*x=k))x=num+i%j;
	printf("並び替え完了\n");
	return (OK);
}
こうすると、ソート部分はもとのコードの半分より少し多いくらいの文字数になり、ループ(for文)も2個から1個に減らすことができました。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: 昇順並び替えの出力

#4

投稿記事 by みけCAT » 9年前

自分の場合、基本的な考え方は「同じ記述が複数ある場所をまとめる」でした。

とりあえず適当に書きます。かなり無駄が多いです。

コード:

int i;for(i=0;i<MAX*(MAX-1);i++)if(num[i%(MAX-1)]>num[i%(MAX-1)+1])num[i%(MAX-1)]^=num[i%(MAX-1)+1],num[i%(MAX-1)+1]^=num[i%(MAX-1)],num[i%(MAX-1)]^=num[i%(MAX-1)+1];
MAX-1の計算と、i%(MAX-1)の計算をまとめます。
num[k=i%j]>num[k+1]としてしまうと、比較演算子の左辺と右辺のどっちが先に計算されるかわからず、
undefined behaviorになってしまうので注意が必要です。

コード:

int i,j=MAX-1,k;for(i=0;i<MAX*j;i++)if(num[k=i%j]>num[i%j+1])num[k]^=num[k+1],num[k+1]^=num[k],num[k]^=num[k+1];
numという長い変数名が大量に出てきているので、nに入れます。

コード:

int*n=num,i,j=MAX-1,k;for(i=0;i<MAX*j;i++)if(n[k=i%j]>n[i%j+1])n[k]^=n[k+1],n[k+1]^=n[k],n[k]^=n[k+1];
n[k]やn[k+1]が大量に出てきているので、ポインタに入れてまとめます。
i%jの計算は2回しか出てこないので、無理にまとめる方がコストが高くなりました。

コード:

int*n=num,*x,*y,i,j=MAX-1;for(i=0;i<MAX*j;i++)if(*(x=n+i%j)>*(y=n+i%j+1))*x^=*y,*y^=*x,*x^=*y;
nも2回しか出てこないので、無理にまとめる方がコストが高くなりました。

コード:

int*x,*y,i,j=MAX-1;for(i=0;i<MAX*j;i++)if(*(x=num+i%j)>*(y=num+i%j+1))*x^=*y,*y^=*x,*x^=*y;
変数宣言のiと初期値の設定のi=0でiを2回書くのは無駄です。まとめましょう。

コード:

int*x,*y,i=0,j=MAX-1;for(;i<MAX*j;i++)if(*(x=num+i%j)>*(y=num+i%j+1))*x^=*y,*y^=*x,*x^=*y;
i++とi<MAX*jでiを2回書くのは無駄です。まとめましょう。
ループの順番が変わりますが、ソートがきちんとできることに変わりはありません。

コード:

int*x,*y,j=MAX-1,i=MAX*j;for(;i--;)if(*(x=num+i%j)>*(y=num+i%j+1))*x^=*y,*y^=*x,*x^=*y;
num+i%jという長い数式が2回書かれています。まとめましょう。
*(x=num+i%j)>*(y=x+1)はundefined behaviorであることに注意が必要です。

コード:

int*x,*y,j=MAX-1,i=MAX*j;for(;i--;(*x>*(y=x+1))&&(*x^=*y,*y^=*x,*x^=*y))x=num+i%j;
よく考えたら条件式に括弧をつける必要はありませんでした。

コード:

int*x,*y,j=MAX-1,i=MAX*j;for(;i--;*x>*(y=x+1)&&(*x^=*y,*y^=*x,*x^=*y))x=num+i%j;
^=という長い演算子が3個もあり、間接演算子*も使われているので、
変数を追加するコストを考えても素直に一時変数に代入したほうがいいでしょう。

コード:

int*x,*y,k,j=MAX-1,i=MAX*j;for(;i--;*x>*(y=x+1)&&(k=*y,*y=*x,*x=k))x=num+i%j;
変数宣言の後の;とfor文の初期化部分の後の;が被っていますね。
for文の初期化部分での変数宣言が許されるC99以降なら、さらに短くできます。

コード:

for(int*x,*y,k,j=MAX-1,i=MAX*j;i--;*x>*(y=x+1)&&(k=*y,*y=*x,*x=k))x=num+i%j;
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: 昇順並び替えの出力

#5

投稿記事 by みけCAT » 9年前

すいません。無駄な変数yを宣言してy=x+1とかいう無駄な式を書くより、添字演算子を使う方が短くなりました。

コード:

int*x,k,j=MAX-1,i=MAX*j;for(;i--;*x>x[1]&&(k=x[1],x[1]=*x,*x=k))x=num+i%j;
これで74文字なので、154文字あったもとのコードに比べて半分以下の長さになりました。

C99以降用は

コード:

for(int*x,k,j=MAX-1,i=MAX*j;i--;*x>x[1]&&(k=x[1],x[1]=*x,*x=k))x=num+i%j;
最後に編集したユーザー みけCAT on 2015年12月29日(火) 15:25 [ 編集 1 回目 ]
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

トワ

Re: 昇順並び替えの出力

#6

投稿記事 by トワ » 9年前

みけCATさん>
ありがとうございます。
えっと、課題自体は赤の部分を考えるもので他は変えなくてもできるようになっています。
(他の部分はプリントでもらったものをそのまま打っています)
警告の方はおそらく他の部分を変えてもいいということだと思います。

閉鎖

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