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