simple quick sort
何年ぶりかに、quick sortを書いてみた。
たぶんこれ以上美しくはかけないと思う。
あくまで独断と偏見だけど。
void quickSort(int *a, int n){ if( n <= 1 ) return; int i=1,j=n-1; int pivot = a[0]; int swp; while( i<j ){ if( a[i] <= pivot ){ i++; }else{ swp = a[i]; a[i] = a[j]; a[j] = swp; j--; } } if( a[i] > pivot ){ i--; } a[0] = a[i]; a[i] = pivot; quickSort(a,i); quickSort(&a[i+1],n-i-1); }
どうして最後の比較と置換が必要になるかというと、
それはwhile実行では最後のiの示す要素の比較が行われていないから。
また{a_{first},pivot,{a_{last}}という感じでピボットを境に前半と後半でソートしたいから。
こんな感じで実行してね。
int main(int argc, char **argv){ if( argc <= 1 ) return 1; int a[argc-1]; int i,j; for(i=0; i<argc-1; i++){ a[i] = atoi(argv[i+1]); } quickSort( a, argc-1 ); for(i=0; i<argc-1; i++){ printf("%d\n",a[i]); } return 0; }