クイックソートとバブルソートの比較回数と交換回数を確認するため以下のようなプログラムを作成しました。
#include <stdio.h>
#define SIZE 32
short bubble_sort(short s[],int x);
short quick_sort(short s[],int y,int z);
void show(short s[],int n);
short bubble_sort(short s[],int x){ //バブルソート
int i,j,count,sum;
short tmp;
count=0;
sum=0;
for(i=0; i<SIZE; i++){
for(j=i+1; j<SIZE; j++){
count++;
if(s[i] > s[j]){
tmp=s[i];
s[i]=s[j];
s[j]=tmp;
sum++;
}
}
}
show(s,SIZE);
printf("\n比較回数:%d回\n交換回数:%d回\n",count,sum);
}
short quick_sort(short s[],int left,int right){ //クイックソート
int i, j,tmp,count,sum;
int point;
i = left;
j = right;
point = s[(left + right) / 2];
count=0;
sum=0;
while (right!=1) {
count++;
while (s[i] < point)
i++;
count++;
while (point < s[j])
j--;
if (i >= j)
break;
tmp=s[i];
s[i]=s[j];
s[j]=tmp;
i++;
j--;
sum++;
}
show(s,SIZE);
printf("\n比較回数:%d回\n交換回数:%d回\n",count,sum);
if (left < i - 1)
quick_sort(s, left, i - 1);
if (j + 1 < right)
quick_sort(s, j + 1, right);
}
void show(short s[], int n)
{
int i;
for (i = 0; i < n ; i++){
printf("%d ", s[i]);
}
printf("\n");
}
int main(void){
short s[SIZE] ={25,29,1,32,14,22,26,3,15,27,5,7,24,12,31,23,6,20,10,8,18,16,11,30,13,2,4,21,17,19,9,28};
printf("ソート前:\n");
show(s,SIZE);
printf("バブルソート後:\n");
bubble_sort(s,SIZE);
printf("\n");
short t[SIZE] ={25,29,1,32,14,22,26,3,15,27,5,7,24,12,31,23,6,20,10,8,18,16,11,30,13,2,4,21,17,19,9,28};
printf("ソート前:\n");
show(t, SIZE);
printf("ソート中:\n");
quick_sort(t,0,SIZE-1);
printf("クイックソート後:\n");
show(t,SIZE);
}
これを動かして頂ければ分かるとは思いますが、バブルソートの時のような結果(途中経過なしで最終結果と比較回数と交換回数の表示)を
クイックソートでも出したいのですが、うまく出せずに困っています。
どのようにすれば良いのかご指導いただけませんでしょうか?また、実行環境が会社にしかないので、
できれば結果も頂けるとありがたいです。失礼ですみませんがよろしくお願い致します。
A 回答 (3件)
- 最新から表示
- 回答順に表示
No.1
- 回答日時:
quick_sortは再帰呼び出しされているので、それを考慮してカウントしないとダメです。
あと、クイックソートにおける比較回数の対象が不明確なので、適当に解釈しました。
#include <stdio.h>
#define SIZE 32
void bubble_sort(short s[],int x);
//short quick_sort(short s[],int y,int z);
void quick_sort(short s[],int y,int z, int *count, int *sum);
void show(short s[],int n);
void bubble_sort(short s[],int x){ //バブルソート
int i,j,count,sum;
short tmp;
count=0;
sum=0;
for(i=0; i<SIZE; i++){
for(j=i+1; j<SIZE; j++){
count++;
if(s[i] > s[j]){
tmp=s[i];
s[i]=s[j];
s[j]=tmp;
sum++;
}
}
}
show(s,SIZE);
printf("\n比較回数:%d回\n交換回数:%d回\n",count,sum);
}
void quick_sort(short s[],int left,int right, int *count, int *sum){ //クイックソート
int i, j,tmp/*,count,sum*/;
int point;
i = left;
j = right;
point = s[(left + right) / 2];
//count=0;
//sum=0;
while (right!=1) {
(*count)++;
while (s[i] < point) {
i++;
(*count)++;
}
(*count)++;
while (point < s[j]) {
j--;
(*count)++;
}
(*count)++;
if (i >= j)
break;
tmp=s[i];
s[i]=s[j];
s[j]=tmp;
i++;
j--;
(*sum)++;
}
//show(s,SIZE);
//printf("\n比較回数:%d回\n交換回数:%d回\n",count,sum);
if (left < i - 1)
quick_sort(s, left, i - 1, count, sum);
if (j + 1 < right)
quick_sort(s, j + 1, right, count, sum);
}
void show(short s[], int n)
{
int i;
for (i = 0; i < n ; i++){
printf("%d ", s[i]);
}
printf("\n");
}
int main(void){
int count=0;
int sum=0;
short s[SIZE] ={25,29,1,32,14,22,26,3,15,27,5,7,24,12,31,23,6,20,10,8,18,16,11,30,13,2,4,21,17,19,9,28};
short t[SIZE] ={25,29,1,32,14,22,26,3,15,27,5,7,24,12,31,23,6,20,10,8,18,16,11,30,13,2,4,21,17,19,9,28};
printf("ソート前:\n");
show(s,SIZE);
printf("バブルソート後:\n");
bubble_sort(s,SIZE);
printf("\n");
printf("ソート前:\n");
show(t, SIZE);
printf("ソート中:\n");
quick_sort(t,0,SIZE-1, &count, &sum);
printf("\n比較回数:%d回\n交換回数:%d回\n",count,sum);
printf("クイックソート後:\n");
show(t,SIZE);
}
純粋なC環境だとエラーになるので、main関数内の変数宣言は前に動かしています。
値を返していない2つの関数も型をvoidに変更してます。
上記を実行した結果は
バブルソート
比較回数:496回
交換回数:271回
クイックソート
比較回数:290回
交換回数:45回
間違ってたらごめんなさい。
No.2
- 回答日時:
quick_sort()の中で、
・countとsumをstaticにする
・countとsumをゼロで初期化しているのをやめる
こうすることで、quick_sort()を再帰的に実行しても
「countとsumを毎回ゼロで初期化する」ことがなくなります。
No.3
- 回答日時:
異論もあろうかとは思いますが・・・。
#include <stdio.h>
#define SIZE 32
int compare, exchange; //禁断のグローバル変数にセット
void bubble_sort(short *,int);
void quick_sort(short *,int,int);
void show(short *,int);
int main(void){
short s[SIZE] ={25,29,1,32,14,22,26,3,15,27,5,7,24,12,31,23,6,20,10,8,18,16,11,30,13,2,4,21,17,19,9,28};
short t[SIZE] ={25,29,1,32,14,22,26,3,15,27,5,7,24,12,31,23,6,20,10,8,18,16,11,30,13,2,4,21,17,19,9,28};
printf("ソート前:\n");
show(s,SIZE);
compare = exchange = 0;
bubble_sort(s,SIZE);
printf("バブルソート後:\n");
show(s,SIZE);
printf("\n比較回数:%d回\n交換回数:%d回\n",compare,exchange);
printf("\n");
printf("ソート前:\n");
show(t, SIZE);
compare = exchange = 0;
quick_sort(t,0,SIZE-1);
printf("クイックソート後:\n");
show(t,SIZE);
printf("\n比較回数:%d回\n交換回数:%d回\n",compare,exchange);
return 0;
}
void bubble_sort(short s[],int x){ //バブルソート
int i,j;
short tmp;
for(i=0; compare++,i<SIZE; i++){
for(j=i+1; compare++,j<SIZE; j++){
if(compare++, s[i] > s[j]){
tmp=s[i];
s[i]=s[j];
s[j]=tmp;
exchange++;
}
}
}
}
void quick_sort(short s[],int left,int right){ //クイックソート
int i,j,point;
short tmp;
i = left;
j = right;
point = s[(left + right) / 2];
while (compare++, right!=1) {
while (compare++, s[i] < point)
i++;
while (compare++, point < s[j])
j--;
if (compare++, i >= j)
break;
tmp=s[i];
s[i++]=s[j];
s[j--]=tmp;
exchange++;
}
if (compare++, left < i - 1)
quick_sort(s, left, i - 1);
if (compare++, j + 1 < right)
quick_sort(s, j + 1, right);
}
void show(short s[], int n){
int i;
for (i = 0; i < n ; i++){
printf("%d ", s[i]);
}
printf("\n");
}
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
このQ&Aを見た人はこんなQ&Aも見ています
-
あるあるbotに投稿したけど採用されなかったあるある募集
あるあるbotに投稿したけど採用されなかったあるあるをこちらに投稿してください
-
フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
あなたが普段思っている「これまだ誰も言ってなかったけど共感されるだろうな」というあるあるを教えてください
-
映画のエンドロール観る派?観ない派?
映画が終わった後、すぐに席を立って帰る方もちらほら見かけます。皆さんはエンドロールの最後まで観ていきますか?
-
海外旅行から帰ってきたら、まず何を食べる?
帰国して1番食べたくなるもの、食べたくなるだろうなと思うもの、皆さんはありますか?
-
天使と悪魔選手権
悪魔がこんなささやきをしていたら、天使のあなたはなんと言って止めますか?
-
C言語クイックソートの比較総回数について教えて下さい
C言語・C++・C#
-
クイックソートの交換回数
C言語・C++・C#
-
GETメソッドとPOSTメソッドの利点と欠点を教えてください
CGI
-
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
std::set<int> で、ある値が何...
-
C#のコンパイルエラーCS0120に...
-
Cでボリュームコントロールを制...
-
int16_t の _t は何?
-
C言語の関数で戻り値を返す必要...
-
fprintfでの文字化け
-
C言語での引数の省略方法
-
因数分解を行うプログラムについて
-
引数 戻り値 return文について
-
演算子オーバーロードのプログ...
-
atoi関数の自作
-
C言語での奇数の和
-
c言語 〇×ゲーム
-
プログラムのバグについて
-
C言語で分からないところがあり...
-
ColorをRGBで指定する方法
-
C言語の基礎 . 2乗値の差につ...
-
剰余演算を論理演算と加減算に...
-
クイックソートでの整列
-
c/c++でのファイルの上書き保存...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
「指定されたキャストは有効で...
-
C言語での引数の省略方法
-
#define _CRT_SECURE_NO_WARNIN...
-
AtCoderABC135の問題Cについて
-
C言語 エラーの原因がわからな...
-
複数桁10進数の*桁目だけを抽出...
-
【C++】関数ポインタの使い方
-
実数の整数部,小数部の取得
-
ラップ関数とはどんなものですか?
-
if と配列の組み合わせ
-
return 1L
-
read関数をノンブロッキングで...
-
(int *)の意味
-
std::set<int> で、ある値が何...
-
Win32APIで作るコンボボックス...
-
C++でvectorにテキストファイル...
-
「{ } で囲むだけ」は正しい?
-
足して100になるような乱数のア...
-
Arduinoのプログラムにエラーが...
-
課題でつまってます・・・
おすすめ情報