2014-10-01から1ヶ月間の記事一覧
今日のテーマ:ソーティングアルゴリズムの比較 ここまで実装してきたアルゴリズムを、入力サイズを変えながら実行時間を比較してみる。 関数ポインタの扱いや、構造体のリテラルの書き方などのよい復習になった。 クイックソートが全域で高速。入力長Nが大…
今日のテーマ:コムソート バブルソートのスワップ対象とする要素の間隔をあけて配列を舐める様子が、櫛をとかすように見えるのでコム(櫛)ソートとよばれる。 10分くらいで書き終わったので、実行時間の測定方法などについてもちょっと調べたりして20分終…
今日のテーマ:基数ソート まず最初に8ビット符号なし整数のバケットソートを実装して、それを利用するような形で32ビット整数の非負数(31ビット符号なし整数の範囲)の基数ソートを実装した。動作確認までほぼ20分ちょうど。 線形リストのループを回すとこ…
今日のテーマ:ヒープソート バイナリヒープを使ったソーティングを実装した。 実装アプローチとしては、配列で領域を確保して添字演算で二分木構造を実現する一般的なもの。 アルゴリズム自体大して難しくないし、過去に何回か書いたことがあるのでさくっと…
※追記あり 今日のテーマ:クイックソート クイックソートは昔から一発で書けた試しがない。 今回も例によって10分くらいで最初の大筋は書き終わったけど、細かい境界条件バグにハマって35分くらいかかった。 はまっていた原因はピボット値の選択方法をサボっ…
今日書いたもの:マージソート スライスの生成と取り回しに混乱して、20分ちょっとオーバするくらいだった。 練習にはわりとよい例題だったと思う。 しかし、マージする部分の論理をもうちょっとクリアに書けないものか。 gistd0759b21f0803d7946ba 次書くも…
今日のテーマ:バブルソート 配列の扱い方の確認のため、バブルソートを実装した。 gistb022a8608c7d090fda8f 明日のテーマ:マージソート 配列の動的確保とかを確認しながらマージソートを実装する。
Go言語の考え方はチュートリアルで大体理解したけど、3日経ったら文法を完全に忘れてしまったので、体で覚えるためにしばらく毎日Goのコードをちょっとだけ書くことにした。 20分で書けるくらいのものをやろうかと考えている。 今日書いたもの とりあえずネ…