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