課題で…。

[坊主]

つぎの擬似コードを参考にして，クイックソートを実行するプログラムを作りな
さい．また，できるだけ，クイックソートが進行していく過程を分かり易く表示するよう
に各自工夫しなさい．

/* 配列a[/url] のp 番目からr 番目までをソートする*/
quick_sort(a, p, r) {
if (p < r) {
q = partition(a, p, r);
quick_sort(a, p, q);
quick_sort(a, q+1, r);
}
}
/* 配列a[/url] のp 番目からr 番目までを分割する*/
partition(a, p, r) {
x = a[p];
i = p - 1;
j = r + 1;
while(1) {
j--; i++;
while(a[j] > x) j--;
while(a < x) i++;
if (i < j) {
y = a;
a = a[j];
a[j] = y;
}
else
return j;
}
}

という課題が出ました。
掲載されていた解説アプリでクイックソートが進む工程は理解できました!!
ただ、上のように作るとなると厳しいです。
よろしくお願いします！

[管理人]

こんにちは。お書きになったプログラムは、このように書き換えると確認できますよ。

#include <stdio.h>

/* 配列a[/url] のp 番目からr 番目までを分割する*/ 
int partition(int a[/url],int p,int r) { 
	int i,j,x,y;
	x = a[p]; 
	i = p - 1; 
	j = r + 1; 

	while(1) { 
		j--; i++; 
		
		while(a[j] > x) j--; 
		while(a < x) i++; 

		if (i < j) { 
			y = a; 	a = a[j];	a[j] = y; 
		} 
		else 
			return j; 
	} 
} 

//aをpからrまでをソート
void quick_sort(int a[/url],int p,int r) { 
	int q;
	if (p < r) { 
		q = partition(a, p, r); 
		quick_sort(a, p, q); 
		quick_sort(a, q+1, r);
	}
}

int main(){
	int a[10]={7,3,5,1,2,3,9,8,7,4};
	quick_sort(a,0,10-1);

	for(int i=0;i<10;i++)
		printf("%d ",a);

	return 0;
}

処理の内容は解説アプリの中でこれでもかとわかりやすく説明したつもりなのですが、
どの辺がおわかりでないでしょうか？

多分、掲示板で文字で説明するより、アプリをじっくりご覧いただいたほうがよくお分かりいただけると思います。

上記プログラムで実際に動かせますので、どのように処理がおこなわれているか目でおってみてください。

[坊主]

ありがとうございます。
自分が表現しにくい部分は「クイックソートが進行していく過程を分かり易く表示するよう
に各自工夫しなさい．」がわかりにくくて…。
それと申し訳ないのですが
実際にコンパイルしてみたところ下のようになりました。
qs.c(38) : error C2143: 構文エラー : ';' が '型' の前にありません。
qs.c(38) : error C2143: 構文エラー : ';' が '型' の前にありません。
qs.c(38) : error C2143: 構文エラー : ')' が '型' の前にありません。
qs.c(38) : error C2143: 構文エラー : ';' が '型' の前にありません。
qs.c(38) : error C2065: 'i' : 定義されていない識別子です。
qs.c(38) : warning C4552: '<' : 演算子にプログラム上の作用がありません。作用を持
つ演算子を使用してください
qs.c(38) : error C2059: 構文エラー : ')'
qs.c(39) : error C2146: 構文エラー : ';' が、識別子 'printf' の前に必要です。
qs.c(39) : error C2144: 構文エラー : '<不明>' は '<不明>' によって先行されなけれ
ばなりません。
qs.c(39) : error C2144: 構文エラー : '<不明>' は '<不明>' によって先行されなけれ
ばなりません。
qs.c(39) : error C2143: 構文エラー : ';' が '識別子' の前にありません。
どこを修正すれば良いでしょうか？

[box]

> どこを修正すれば良いでしょうか？

おそらく、38行目～39行目あたりです。
具体的にどのように修正すればよいかは、
ソースコードが見えないため、残念ながらわかりません。

[管理人]

エラーを見る限り、簡単な間違いである可能性が高いです。
ソースを一度投稿してもらえませんか？

[坊主]

実際に書いていただいたソースなんですよ…

#include <stdio.h>

/* 配列a[/url] のp 番目からr 番目までを分割する*/
int partition(int a[/url],int p,int r) {
int i,j,x,y;
x = a[p];
i = p - 1;
j = r + 1;

while(1) {
j--; i++;

while(a[j] > x) j--;
while(a < x) i++;

if (i < j) {
y = a; a = a[j]; a[j] = y;
}
else
return j;
}
}

//aをpからrまでをソート
void quick_sort(int a[/url],int p,int r) {
int q;
if (p < r) {
q = partition(a, p, r);
quick_sort(a, p, q);
quick_sort(a, q+1, r);
}
}

int main(){
int a[10]={7,3,5,1,2,3,9,8,7,4};
quick_sort(a,0,10-1);

for(int i=0;i<10;i++)
printf("%d ",a);

return 0;
}

です。

[box]

> 	for(int i=0;i<10;i++)

Cでは、この書き方はできません。C++ならできます。
変数iの定義は、今回の場合、配列aの定義の直前か直後で行なってください。

なお、ソースコードを貼り付ける際は、
＜pre＞
ソース本体
＜/pre＞
のように、前後をタグではさんでください。不等号は半角です。

[坊主]

ありがとうございます！