文字配列のソートと空白文字の対応

Question

大学にてC言語を学んでいます。
以下、問です。
英小文字だけからなるアルファベットの文字列を a から昇順に並べ替えるプログラムを作成しなさい
なお，このプログラムは空白も無視せず並べ替えの対象となるようにしなさい

入力

• 英小文字だけからなるアルファベットの文字列（50文字まで対応）
• 標準入力から読み込む

出力

• aから昇順に並べかえられた文字列
• 標準出力に書き出す
• スペースの出力はハイフン - に置換する

条件として、

• 配列は2つ使用してよい
• for文やwhile文など，反復は入出力処理を除き1つまで
• 変数は配列を除き4つまで（3つでも可能）
• コードはできるだけ18行以内におさめること（コメントや空行，括弧だけの行などは除く）
• if文などの条件分岐は用いない
• 入力文字列の長さは50文字まで対応すること
• フラグを用いた処理はしない

for2つの場合はできるのですが…1つに制限されてしまって困っています。また、qsort関数などを使用せず組むやり方も可能であればよろしくお願いします。

Comments

[jimbe]

>for2つの場合はできるのですが

出来ているコードをご提示願えますか。
それと、用いる文字コード(シフトJIS とか Unicode とか EBCDIC とか) は何前提でしょう。

[fana]

> 空白も無視せず並べ替えの対象となるように

空白は並べ替えた結果としてはどこに行けばいいのか？
例えば入力が "b_a" のとき（←のアンダーバーが空白なのだとして）出力は
"a-b"
"-ab"
"ab-"
のどれになるのか？

[episteme]

> 英小文字だけからなるアルファベットの文字列
> 空白も無視せず並べ替えの対象となる

英小文字だけからなるのなら、空白を含まないのでは?

[jikijikidon]

文字コードはASCIIコードを用います。
実行例を出すのを忘れていました。申し訳ないです。

以下、実行例です。
super califragilistic expiali docious
---aaacccdeefgiiiiiiillloopprrssstuux

[jimbe]

50文字の入力→50文字のソートでは無く、[1文字の入力→1文字(とそれまでの入力)のソート]を50回と言うのはセーフでしょうか？

Answer 1

#include <stdio.h>   // fgets, putchar
#include <string.h>  // strlen

int main(void)
{
	char s[53];
	fgets(s, 52, stdin);
	int i, n = strlen(s) - 1;
	for (i = 0; i < n*n; i++)
		i/n < i%n && s[i/n] > s[i%n] &&
			(s[52] = s[i/n], s[i/n] = s[i%n], s[i%n] = s[52]);
	for (i = 0; s[i]; i++) putchar((s[i]==' ')*'-' + (s[i]!=' ')*s[i]);
}

どこが分からないのかをコメントしてください。
追記
ソートをバブルソートに変えてみると、

#include <stdio.h>   // fgets, putchar
#include <string.h>  // strlen

int main(void)
{
	char s[53];
	fgets(s, 52, stdin);
	int i, n = strlen(s) - 1;
	for (i = 0; i < n*n; i++)
		i%n && s[i%n-1] > s[i%n] &&
			(s[52] = s[i%n-1], s[i%n-1] = s[i%n], s[i%n] = s[52]);
	for (i = 0; s[i]; i++) putchar((s[i]==' ')*'-' + (s[i]!=' ')*s[i]);
}

Answer 2

条件を満たすために
main() 内は気合で27個処理を並べることでループを１個潰したけど，
F() の中身が条件に抵触するか否か…？

int H[ 2 + 26 ] = { 0 };	//配列１個目
int Idx( char c ){	return (c==' ')*27 + ('a'<=c && c<='z')*(c-'a'+1);	}  //文字cに対応する H[] のindexを返す

//配列の中身を書き換える作業．
//sの指す先からn文字をcに変えて，その次の位置を返す
char *F( char *s, char c, int n )
{
	*s = (n<=0)**s + (n>0)*c;
	return ( n<=0  ?  s  :  F(s+1,c,n-1) );  //ココが「if等の条件分岐」や「反復」と見なされるならアウト
}

//これは H[] の値を用いての F を呼び出しを簡単に書くだけのヘルパ．
void G( char **s, char c ){	*s = F( *s, c, H[Idx(c)] );	}

int main()
{
	char Str[50+1];	//配列２個目
	gets_s( Str, 50 );	//入力
	
	char *p = Str;
	while( *p ){	++H[ Idx(*p) ];	++p;	}	//ループ

	char *s = F( Str, '-', H[27] );
	G( &s,'a' );	G( &s,'b' );	G( &s,'c' );	G( &s,'d' );	G( &s,'e' );	G( &s,'f' );
	G( &s,'g' );	G( &s,'h' );	G( &s,'i' );	G( &s,'j' );	G( &s,'k' );	G( &s,'l' );
	G( &s,'m' );	G( &s,'n' );	G( &s,'o' );	G( &s,'p' );	G( &s,'q' );	G( &s,'r' );
	G( &s,'s' );	G( &s,'t' );	G( &s,'u' );	G( &s,'v' );	G( &s,'w' );	G( &s,'x' );
	G( &s,'y' );	G( &s,'z' );

	printf( "%s\n", Str );	//出力
	return 0;
}

Comments

[fana]

> 変数は配列を除き4つまで

の個数として関数引数もカウントされるとかいう話だと，もう全然ダメだが．
（つーか，main関数内の pとs は同じの使えば良かったな）

[fana]

関数Fの実装にいちゃもんが付く場合は，
main内のwhileループの箇所を（怒涛のG呼び出しと同様に）怒涛の50連記述にして，
Fの側を素直にループで書いて解決ってことで．

[fana]

行数については，怒涛の記述を横に並べるとかすればおｋ．

Answer 3

バケットソートをかければ、頻度計量分で反復1回、頻度用にint[80]あたりをとって配列一個。
ループを多めに回すことで、頻度の計算と、結果の出力を一つのfor文にしている。スペースa-zは0x1fでANDをとるときれいいに0~27にならぶ。
if文で条件分岐できなくても、条件式の結果が1/0に成ることを利用した制御とか、ループ変数を書き換えるのは本来的には禁じ手とおもう。

#include <stdio.h>
#include <string.h>
int main()
{
     char str[51];
     int bin[80] = {0};
     int len;
     char *wp = str;
     int i;
//input
     scanf("%50s", str );

//process
     len = strlen( str );
     for( i=0; i<len+27; i++){
          bin[ (str[i%len]&0x1f)+len] += i<len;

          wp += sprintf(wp, "%*.*s", bin[i]>0, bin[i]>0, &"-abcdefghijklmnopqrstuvwxyz"[i-len] );
          bin[i] -= (i>=len)*(bin[i] > 0);
          i -= (i>=len)*(bin[i] > 0);
     }
//output
     printf("%s\n", str );
}

Answer 4

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

int comp(const void* x, const void* y) {
  // ここはアナタが考えて
}

int main(void) {
  char str[51];
  gets(str);
  qsort( /*ココは*/,  /*アナタが*/, /*考えて*/, comp);
  for ( const char* p = str; *p; ++p ) {
    putchar( *p == ' ' ? '-' : *p);
  }
  return 0;
}

Answer 5

ソートの中には、"実際には元のデータは並び替えずに、並び替えたデータを作り出す" ソートというのもあります。

---

c で行数制限などほぼ無意味なのに…。

#include <stdio.h>
#define M 50 //処理可能最大文字列長
#define N 27 //ソート対象文字(b)の文字数
int main(void){
  int i, j, c; //(配列以外の)変数
  char a[N+1]={0}, b[N+1]=" abcdefghijklmnopqrstuvwxyz"; //配列
  for(i=0; i<M && (c=getchar())!=EOF; i++) //入力(これは入力の為のループなのです!)
    { for(j=0; j<N && b[j]!=c; j++); a[j]++; } //処理
  for(i=0, b[0]='-'; i<N; i++) for(j=0; j<a[i]; j++) putchar(b[i]); putchar('\n'); //出力
}

brick quiz whangs jumpy veldt fox.
-----abcdefghiijklmnopqrstuuvwxyz

super califragilistic expiali docious
---aaacccdeefgiiiiiiillloopprrssstuux

matukeso さんの『 0x1f で AND 』を用いれば、処理の行は a[c & 0x1f]++; だけになるので、ループの制限は問題無さそうで、そしたらいっそ b も無くして出力もfor(i=0; i<N; i++) for(j=0; j<a[i]; j++) putchar(i+(i?0x60:0x2d)); putchar('\n'); ですかねぇ。

---

分布数えソート。
a に入力して b の後半にカウントして a に並べて(もしくは直接)出力。並べる部分が処理だと言われそう。

#define __STDC_WANT_LIB_EXT1__ 1
#include <stdio.h>
#define M 50 //処理可能最大文字列長
#define N 27 //ソート対象文字(b)の文字数
int main(void) {
  char *t, *p; //(配列以外の)変数
  char a[M+1], b[N+1+N]=" abcdefghijklmnopqrstuvwxyz"; //配列
#ifdef __STDC_LIB_EXT1__
  gets_s(a, M+1); //入力
#else
  gets(a); //入力
#endif
  for(t=a, p=b; *p; *++t||(t=a,p++)) p[N+1]+=(*t==*p); //処理
  for(t=a, p=b, b[0]='-'; *p; p++) while(p[N+1]--) *t++=*p; *t='\0'; printf("%s\n", a); //a に展開して出力
  //for(p=b, b[0]='-'; *p; p++) while(p[N+1]--) putchar(*p); putchar('\n'); //直接出力(こっちの方が出力のためのループっぽい)
}

---

選択(外部)ソート(?)。
a に入力して並び順に選んで b に溜めて出力。

#define __STDC_WANT_LIB_EXT1__ 1
#include <stdio.h>
#define M 50 //処理可能最大文字列長
int main(void) {
  char a[M+1], b[M+1]; //配列
#ifdef __STDC_LIB_EXT1__
  gets_s(a, M+1); //入力
#else
  gets(a); //入力
#endif
  //(配列以外の)変数: i=入力文字, p=並び順文字+転記文字, o=出力先
  char *i=a, *p=" -aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzz", *o=b;
  for(; *p; *++i||(i=a,p+=2)) *p==*i&&(*o++=p[1]); *o='\0'; //処理
  printf("%s\n", b); //出力
}

---

選択ソート(コード依存)。

#define __STDC_WANT_LIB_EXT1__ 1
#include <stdio.h>
#define M 50 //処理可能最大文字列長
int main(void) {
  char a[M+1]; //配列
#ifdef __STDC_LIB_EXT1__
  gets_s(a, M+1); //入力
#else
  gets(a); //入力
#endif
  char *p=a, *q=p+1, c; //(配列以外の)変数
  for(; *p&&(*q||(*p==' '&&(*p='-')&&0)); *++q||(q=++p+1)) *p>*q&&(c=*q,*q=*p,*p=c); //処理
  printf("%s\n", a); //出力
}