ALDS1_6_B: Partition

問題へのリンク

C#のソース

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

// Q018 パーティション https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_B&lang=jp
class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("12");
            WillReturn.Add("13 19 9 5 12 8 7 4 21 2 6 11");
            //9 5 8 7 4 2 6 [11] 21 13 19 12
        }
        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 ResultPartition = Partition(AArr, 0, AArr.GetUpperBound(0));

        var StrList = new List<string>();
        for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
            if (I == ResultPartition) {
                StrList.Add(string.Format("[{0}]", AArr[I]));
            }
            else {
                StrList.Add(AArr[I].ToString());
            }
        }
        Console.WriteLine(string.Join(" ", StrList.ToArray()));
    }

    static int Partition(int[] pArr, int p, int r)
    {
        int x = pArr[r];
        int I = p - 1;
        for (int J = p; J <= r - 1; J++) {
            if (pArr[J] <= x) {
                I++;
                int Swap1 = pArr[I];
                pArr[I] = pArr[J];
                pArr[J] = Swap1;
            }
        }
        int Swap2 = pArr[I + 1];
        pArr[I + 1] = pArr[r];
        pArr[r] = Swap2;
        return I + 1;
    }
}

解説

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