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

今年度の目標は

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

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

強くなりたいんじゃ。

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

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

バブルソート

#

O(n^2)

選択ソート

#

O(n^2)

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

挿入ソート

#

O(n^2)

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

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

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

マージソート

#

計算時間

#

O(nlogn)

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

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

(Wikipediaより)

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

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

以下コード。C#です。

using System.Collections;
using System.Collections.Generic;
using System;

public static class MergeSort
{
    /// <summary>
    ///基本的な手順は以下の通りである。
    ///1.データ列を分割する（通常、等分する）
    ///2.各々をソートする
    ///3.二つのソートされたデータ列をマージする
    ///これを再帰的に
    ///コード的には
    ///最小粒度まで分割->最下層からソートしながらマージ
    ///なイメージ
    ///計算量O(nlogn)
    ///合わせて長さNの配列をソートしながらマージする時の比較回数　= N = 計算時間O(n)　
    ///長さNの配列の木の深さ = logN
    ///から計算時間NlogNがざっくりわかる
    /// </summary>
    public static int[] Sort(int[] target)
    {
        int l=target.Length;

        //長さが1なのでソートできない（ソート済みとみなす）
        if(l<=1){
            return target;
        }

        //分割する
        int[] left;
        int[] right;
        SplitHalf(target,out left,out right);

        left = Sort(left);
        right = Sort(right);

        //ソートされた左右をソートを崩さずマージ
        return MergeWithSort(left,right);
    }

    static void SplitHalf(int[] target,out int[] left,out int[] right )
    {
        int leftLength = target.Length/2;
        int rightLength = target.Length - leftLength;
        left = new int[leftLength];
        right = new int[rightLength];
        for(int i = 0;i<target.Length;i++){
            if(i < leftLength){
                left[i] = target[i];
            }else{
                right[i-leftLength] = target[i];
            }
        }
        //自前の方がちょっと早い?n=50000で2ミリ秒くらい
        // Array.Copy(target, 0,left, 0, leftLength);
        // Array.Copy(target, leftLength,right, 0, rightLength);
    }

    static int[] MergeWithSort(int[] left,int[] right)
    {
        var result = new int[left.Length + right.Length];
        int resultIndex = 0;
        int leftIndex = 0;
        int rightIndex = 0;
        //どちらかがなくなるまで両方をくらべながら小さい方を結果に詰めていく
        while(leftIndex < left.Length && rightIndex < right.Length){
            if(left[leftIndex] < right[rightIndex])
            {
                result[resultIndex] = left[leftIndex];
                leftIndex++;
            }
            else
            {
                result[resultIndex] = right[rightIndex];
                rightIndex++;
            }
            resultIndex ++;
        }

        //なくなりきっていなければそのまま詰める(ソートはすでにされている)
        //左右どちらかは絶対になくなっている
        for(int l = left.Length;leftIndex < l;leftIndex++){
            result[resultIndex]=left[leftIndex];
            resultIndex ++;
        }
        for(int l = right.Length;rightIndex < l;rightIndex++){
            result[resultIndex]=right[rightIndex];
            resultIndex ++;
        }

        return result;
    }
}

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

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

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

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

ではまた。