yashiganiの英傑になるまで死ねない日記

週末はマスターバイクでハイラルを走り回ります

バブルソートを修正してみた

研究室の先輩から“比較回数はn(n-1)/2”だという指摘を受け修正してみた.

#include <stdio.h>

void printVal(int *val, int length){
	int i;

	for(i = 0; i < length; i++)
		printf("%3d", val[i]);
	printf("\n");
}

int *swap(int *val, int a, int b){
	int temp;

	temp = val[a];
	val[a] = val[b];
	val[b] = temp;

	return val;
}

void bsort(int *val, int length){
	int i, j;

	for(i = length; i > 0; i--){
		for(j = 0; j < i - 1; j++){
			printf("compare %d, %d \n", val[j], val[j + 1]);
			printVal(val, length);
			if(val[j] > val[j + 1])
				swap(val, j, j + 1);
		}
	}

}

int main(int argc, char *argv[]){
	int val[5] = {31, 8, 24, 2, 5};
	int i = 0;

	printf("start \n");
	printVal(val, 5);
	bsort(val, 5);
	printf("end \n");
	printVal(val, 5);
}

これで比較回数は10回になりました.
“大きい要素から右にポツポツでてくるからバブルソート”っていうことばっかり頭にあって“大きい要素から順に整列される”ってことがきれいさっぱり頭から抜けていたことが失敗でした.
あと,再帰を使いたがったことも失敗.
だんだん整列する範囲を狭めたいので二重ループにすればよかったわけです.
やっぱり分析と設計って大事ですね.