9件中 1-5件目     [ 1 2 ]

標準入力に何かを入力させて処理をするプログラムをデバッグする場合、何度も同じ入力を繰り返すことがよくある。そんなときには入力データをファイルとして用意して、パイプとリダイレクションを使ってファイルに入出力をすると便利だが、それ以外にもfreopen関数を使う方法もある。Windows上でVisual Studioのような統合開発環境を使って開発をしている場合には、こちらの方が便利かもしれない。


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

シェルソートの実行例

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


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

記念品と賞状

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

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


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


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


9件中 1-5件目     [ 1 2 ]