Programming Magic

シェルソートは挿入ソートを改良したソートアルゴリズムで、データを間隔hごとのグループに分けてそれぞれ挿入ソートを行うという操作を、hを徐々に減らしながら繰り返しデータ全体をソートする。

単純に考えるとシェルソートは挿入ソートを繰り返し実行しているので挿入ソートよりも遅くなりそうだが、交換回数が少なくなるので高速にソートすることができる。 シェルソートでは間隔hの決め方が重要で、実際に実験してみたところ間隔hを変えるだけで実行速度に10倍以上の差が出た。

今回はコンテスト終了まで残り24時間の時点で総合8位くらい(973852点)だったのでTOP3に入るのは無理だと思って諦めていたが、意外とスコアが伸びて最終的に学生部門で2位、総合部門で3位となった。

ソースコードはコンテストの結果発表ページに掲載されているのでそちらを参照。 (ソースコード上部のコメント内にアルゴリズムの解説あり。)

去年もコンテスト終了後に次回の参加者向けにアドバイスを書いたが、今年新しく学んだこともあるので今年も少し書いておこうと思う。

以前『全ての組み合わせを作る[C++]』で書いたnext_combination関数を使えば、全ての重複組み合わせを作るのも簡単にできそうだったので作ってみた。

c++には可変長配列のstd::vectorがあるが、std::vectorでは配列の範囲外にアクセスしたときに自動でサイズを拡張せずにエラーを吐くため、値を代入するときにサイズをチェックしなければならないことがある。勝手にサイズが拡張されてしまうとバグを見逃す可能性が増えるため一長一短ではあるが、テスト用コードを書く場合などはいちいちサイズをチェックしなくても勝手にサイズを拡張してほしい。

C++で全ての順列を作りたければ、STLにnext_permutation関数があり、以下のように簡単に作ることができる。

#include <iostream>
#include <vector>
#include <algorithm>

int main(){
  const int n = 3;
  std::vector<int> data;
  // [0, 1, 2, ....]というサイズnの配列を作成
  for(int i=0; i<n; ++i){
    data.push_back(i);
  }
  // 全ての順列を出力
  do{
    std::cout << "[ " << data[0];
    for(unsigned int i=1; i<data.size(); ++i){
      std::cout << ", " << data[i];
    }
    std::cout << " ]" << std::endl;
  }while(next_permutation(data.begin(), data.end()));

  return 0;
}

[ 0, 1, 2 ]
[ 0, 2, 1 ]
[ 1, 0, 2 ]
[ 1, 2, 0 ]
[ 2, 0, 1 ]
[ 2, 1, 0 ]

しかし、STLには同じように組み合わせを作るための関数が存在しない。そこで全ての組み合わせを作るような関数を探してみた。