ALDS1_6_C: Quick Sort

問題へのリンク

C#のソース

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

// Q019 クイックソート https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_C&lang=jp
class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("6");
            WillReturn.Add("D 3");
            WillReturn.Add("H 2");
            WillReturn.Add("D 1");
            WillReturn.Add("S 3");
            WillReturn.Add("D 2");
            WillReturn.Add("C 1");
            //Not stable
            //D 1
            //C 1
            //D 2
            //H 2
            //D 3
            //S 3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("S 1");
            WillReturn.Add("H 1");
            //Stable
            //S 1
            //H 1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct CardInfoDef
    {
        internal char Suit;
        internal int Num;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        var CardInfoList = new List<CardInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            string[] SplitArr = EachStr.Split(' ');
            CardInfoDef WillAdd;
            WillAdd.Suit = SplitArr[0][0];
            WillAdd.Num = int.Parse(SplitArr[1]);
            CardInfoList.Add(WillAdd);
        }

        CardInfoDef[] QuickArr = CardInfoList.ToArray();
        CardInfoDef[] MergeArr = CardInfoList.ToArray();

        QuickSort(QuickArr, 0, QuickArr.GetUpperBound(0));
        MergeSort(MergeArr, 0, MergeArr.GetUpperBound(0) + 1);

        if (QuickArr.SequenceEqual(MergeArr)) {
            Console.WriteLine("Stable");
        }
        else {
            Console.WriteLine("Not stable");
        }
        Array.ForEach(QuickArr, pX => Console.WriteLine("{0} {1}", pX.Suit, pX.Num));
    }

    static void QuickSort(CardInfoDef[] pArr, int p, int r)
    {
        if (p < r) {
            int q = Partition(pArr, p, r);
            QuickSort(pArr, p, q - 1);
            QuickSort(pArr, q + 1, r);
        }
    }

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

    static void MergeSort(CardInfoDef[] Arr, int left, int right)
    {
        if (left + 1 < right) {
            int mid = (left + right) / 2;
            MergeSort(Arr, left, mid);
            MergeSort(Arr, mid, right);
            Merge(Arr, left, mid, right);
        }
    }

    static void Merge(CardInfoDef[] Arr, int left, int mid, int right)
    {
        int n1 = mid - left;
        int n2 = right - mid;
        CardInfoDef[] L = new CardInfoDef[n1 + 1];
        CardInfoDef[] R = new CardInfoDef[n2 + 1];
        for (int I = 0; I <= n1 - 1; I++) {
            L[I] = Arr[left + I];
        }
        for (int I = 0; I <= n2 - 1; I++) {
            R[I] = Arr[mid + I];
        }
        L[n1].Num = int.MaxValue;
        R[n2].Num = int.MaxValue;

        int LoopI = 0, LoopJ = 0;
        for (int LoopK = left; LoopK <= right - 1; LoopK++) {
            if (L[LoopI].Num <= R[LoopJ].Num) {
                Arr[LoopK] = L[LoopI++];
            }
            else {
                Arr[LoopK] = R[LoopJ++];
            }
        }
    }
}

解説

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