マージソート :C#でLet’sデルゴリ(データ構造とアルゴリズム)

年度が変わったせいかなんか強くなりてえなあという気持ちになってきたので本気でデータ構造とアルゴリズムやら競技プログラミングやらをやっていこうと思います。

今年度の目標は

  1. アルゴリズムの基礎を抑える
  2. AtCorderで黄色になる

AtCorderの黄色がどんなもんか詳しくわかってないけど多分結構強いはず。

強くなりたいんじゃ。

ということで、ゲーム作りとWebサービス作りは一旦休止。ゲーム作りにいたっては始めたばっかですが、普通にしんどいので一旦やめます。

ではではとりあえず基本のアルゴリズム、ソート。

バブルソート

O(n^2)

選択ソート

O(n^2)

「比較回数」は同じだが「交換回数」が少ないのでバブルソートより早い。

挿入ソート

O(n^2)

「交換回数」は同じだが「比較回数」が少ないのでバブルソートより高速。もともとある程度整列されているデータならさらに早い。

この三つはとりあえず簡単だったので飛ばしちゃう。気が向いたら書くかも。Wikipedia見ればわかる。

今日の本題はマージソート

マージソート

計算時間

O(nlogn)

基本的な手順は以下の通りである。

  1. データ列を分割する(通常、等分する)
  2. 各々をソートする
  3. 二つのソートされたデータ列をマージする

(Wikipediaより)

最小粒度まで分割してソートしながらマージしていく。

へ〜って感じですがコード書くの結構(超)手こずった。再帰的に書くのって難しいですね。

以下コード。C#です。

SplitHalfとかもうちょっとおしゃれな実装したかったんですが思いつきません。知ってたら教えてください。

は〜疲れた。あってるのか心配ですが、まあいろんなとこ見た感じ多分あってます。

なんとなくわかったのでこの調子でアルゴリズムというものとこういう系のコード書くのに慣れていきたい気持ちです。

でかい運用ゲームのコード書くのとは使う脳が違う気がします。

ではまた。

にほんブログ村 IT技術ブログへ
おすすめ一覧

おすすめのサーバ

ミニバード :初心者向け。安くて簡単でWordPressブログ5個まで作れます。250円。

ロリポップ :初心者向け。250円~使えてお安い。500円のがかなり強くておすすめ。老舗で安心。

Conoha:中級者向け。安くクラウドを使ってみたい人におすすめ。時間定額なのでクラウド破産の心配なし。

おすすめのドメイン会社

スタードメイン ミニバード とセットで管理が楽。ついでにポイントももらえてお得。

名づけてねっと :キャンペーンやってておとく

その他おすすめ

Udemy :ビデオ講座は本当に捗るのでマジでおすすめです。

スポンサーリンク

コメントをどうぞ

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です