比較回数と交換回数表示について

質問

クイックソートとバブルソートの比較回数と交換回数を確認するため以下のようなプログラムを作成しました。
#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);
}

これを動かして頂ければ分かるとは思いますが、バブルソートの時のような結果（途中経過なしで最終結果と比較回数と交換回数の表示）を
クイックソートでも出したいのですが、うまく出せずに困っています。

どのようにすれば良いのかご指導いただけませんでしょうか？また、実行環境が会社にしかないので、
できれば結果も頂けるとありがたいです。失礼ですみませんがよろしくお願い致します。

回答No.3

和泉 博（@hiroshi09s）

異論もあろうかとは思いますが・・・。

#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");
}

回答No.2

asuncion

quick_sort()の中で、
　・countとsumをstaticにする
　・countとsumをゼロで初期化しているのをやめる
こうすることで、quick_sort()を再帰的に実行しても
「countとsumを毎回ゼロで初期化する」ことがなくなります。

回答No.1

magicalpass

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関数内の変数宣言は前に動かしています。
値を返していない２つの関数も型をvoidに変更してます。

上記を実行した結果は

バブルソート
比較回数:496回
交換回数:271回

クイックソート
比較回数:290回
交換回数:45回

間違ってたらごめんなさい。