ALDS1_6_A: Counting Sort

問題へのリンク

C#のソース

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

// Q020 計数ソート https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_A&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("7");
            WillReturn.Add("2 5 1 3 2 3 0");
            //0 1 2 2 3 3 5
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();
        int[] BArr = new int[AArr.Length];
        CountingSort(AArr, BArr, AArr.Max());

        Console.WriteLine(string.Join(" ", Array.ConvertAll(BArr, pX => pX.ToString())));
    }

    static void CountingSort(int[] pA, int[] pB, int pK)
    {
        int[] CArr = new int[pK + 1];

        // C[i] に i の出現数を記録する
        for (int J = 0; J <= pA.GetUpperBound(0); J++) {
            CArr[pA[J]]++;
        }

        // 累積和を求める
        for (int I = 1; I <= CArr.GetUpperBound(0); I++) {
            CArr[I] += CArr[I - 1];
        }

        // 0オリジンなので1ずつデクリメント
        for (int J = 0; J <= CArr.GetUpperBound(0); J++) {
            CArr[J]--;
        }

        // 安定ソートにしたいので、配列を逆順に走査
        for (int J = pA.GetUpperBound(0); 0 <= J; J--) {
            int wkInd1 = pA[J];
            int wkInd2 = CArr[wkInd1];
            pB[wkInd2] = pA[J];
            CArr[pA[J]]--;
        }
    }
}

解説

疑似コードをC#で実装してます。