yashigani?.days

週刊少年ジャンプについてだらだら書きます

バブルソートを書いてみた

単位的な問題で3回にもなってデータ構造とアルゴリズムの講義を取っています.
1回生にはゆとりやんちゃな子が多くて,講義はとてもカオスにぎやかです.

いつもはひっそり本を読んですごしているのですが,ちょうどバブルソートの話題になったので暇つぶしに1回生の気分になって実装してみました.

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

int bsort(int *val, int i, int length){
	if(i + 1 >= length)
		return -1;

	//printf("compare %d, %d \n", val[i], val[i + 1]);

	if(val[i] > val[i + 1]){
		val = swap(val, i, i + 1);
		//printVal(val, length);
		bsort(val, i + 1, length);
		bsort(val, i, length);

		return 1;
	}
	else if(val[i] <= val[i + 1]){
		//printVal(val, length);
		return 0;
	}
}

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, 0, 5);
	printf("end \n");
	printVal(val, 5);
}

バブルソートの計算量はO(n^2)なので,要素数が5の場合比較回数は15回になるはずだったのですが,なぜか16回比較しています.
どこがおかしいんだ?