ALDS1_2_C: Stable Sort

問題へのリンク

C#のソース

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

// Q005 安定なソート https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_C&lang=jp
class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("5");
            WillReturn.Add("H4 C9 S4 D2 C3");
            //D2 C3 H4 S4 C9
            //Stable
            //D2 C3 S4 H4 C9
            //Not stable
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("S1 H1");
            //S1 H1
            //Stable
            //S1 H1
            //Stable
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string[] NArr = InputList[1].Split(' ');

        string[] BubbleArr = (string[])NArr.Clone();
        string[] SelectionArr = (string[])NArr.Clone();

        BubbleSort(BubbleArr);
        SelectionSort(SelectionArr);

        Console.WriteLine(string.Join(" ", BubbleArr));
        Console.WriteLine("Stable");
        Console.WriteLine(string.Join(" ", SelectionArr));

        if (BubbleArr.SequenceEqual(SelectionArr)) {
            Console.WriteLine("Stable");
        }
        else {
            Console.WriteLine("Not stable");
        }
    }

    static void BubbleSort(string[] pArr)
    {
        for (int I = 0; I <= pArr.GetUpperBound(0); I++) {
            for (int J = pArr.GetUpperBound(0); I + 1 <= J; J--) {
                if (CardCompare(pArr[J], pArr[J - 1]) < 0) {
                    string Swap = pArr[J];
                    pArr[J] = pArr[J - 1];
                    pArr[J - 1] = Swap;
                }
            }
        }
    }

    static void SelectionSort(string[] pArr)
    {
        for (int I = 0; I <= pArr.GetUpperBound(0); I++) {
            int MinJ = I;
            for (int J = I; J <= pArr.GetUpperBound(0); J++) {
                if (CardCompare(pArr[J], pArr[MinJ]) < 0) {
                    MinJ = J;
                }
            }
            string Swap = pArr[I];
            pArr[I] = pArr[MinJ];
            pArr[MinJ] = Swap;
        }
    }

    static int CardCompare(string pA, string pB)
    {
        int AVal = int.Parse(pA.Substring(1));
        int BVal = int.Parse(pB.Substring(1));
        return AVal.CompareTo(BVal);
    }
}

解説

LINQのSequenceEqual拡張メソッドで順序が一致するかをチェックしてます。