1

マージソートに入る最初の試みとして、リストよりも扱いやすいため、文字列で機能する次のコードを作成しました。

class Program
{
    static int iterations = 0;
    static void Main(string[] args)
    {            
        string test = "zvutsrqponmlihgfedcba";
        test = MergeSort(test);
        // test is sorted after 41 iterations
    }

    static string MergeSort(string input)
    {
        iterations++;
        if (input.Length < 2)
            return input;
        int pivot = 0;
        foreach (char c in input)
            pivot += c;
        pivot /= input.Length;
        string left = "";
        string right = "";
        foreach (char c in input)            
            if (c <= (char)pivot)
                left += c;
            else
                right += c;            
        return string.Concat(new string[] { MergeSort(left), MergeSort(right) });
    }
}

ウィキペディアで考えられる最適化について読んでいると、次のヒントが見つかりました。「最大で O(log N) のスペースが使用されていることを確認するには、最初に配列の小さい方の半分に再帰し、末尾呼び出しを使用して他方に再帰します。」しかし、正直なところ、これを私のケースに適用する方法がわかりません。再帰と階乗について教えられたときに、IT クラスでテール コールを行った漠然とした記憶がありますが、Wikipedia のアドバイスを自分のコードに適用する方法が本当にわかりません。

どんな助けでも大歓迎です。

4

2 に答える 2

3

これは、MergeSort ではなく、最適とは言えない QuickSort の変種のように見えます。この部分に相当する C# がありません。

function merge(left, right)
    var list result
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
            if first(left) <= first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append first(left) to result
            left = rest(left)
        else if length(right) > 0
            append first(right) to result
            right = rest(right)
    end while
    return result
于 2013-05-23T18:01:31.827 に答える