stable_sort

stableSort.cs

<Query Kind="Program">
  <Reference>&lt;RuntimeDirectory&gt;\System.dll</Reference>
  <Reference>&lt;RuntimeDirectory&gt;\System.Net.dll</Reference>
  <Reference>&lt;RuntimeDirectory&gt;\System.Net.Http.dll</Reference>
  <NuGetReference>Microsoft.Net.Http</NuGetReference>
  <NuGetReference>Newtonsoft.Json</NuGetReference>
  <NuGetReference>Sendgrid</NuGetReference>
  <Namespace>Newtonsoft.Json</Namespace>
  <Namespace>Newtonsoft.Json.Bson</Namespace>
  <Namespace>Newtonsoft.Json.Converters</Namespace>
  <Namespace>Newtonsoft.Json.Linq</Namespace>
  <Namespace>Newtonsoft.Json.Schema</Namespace>
  <Namespace>Newtonsoft.Json.Serialization</Namespace>
  <Namespace>SendGrid.SmtpApi</Namespace>
  <Namespace>System.IO</Namespace>
  <Namespace>System.Net</Namespace>
</Query>
void Main()
{
	var n = int.Parse(Console.ReadLine());
	var c = Console.ReadLine().Split(' ');
	
	var bubbleSorted = BubbleSort(c, n);
	Console.WriteLine(string.Join(" ", bubbleSorted));
	Console.WriteLine(IsStable(c, bubbleSorted) ? "Stable" : "Not stable");
		
	var selectionSorted = SelectionSort(c, n);
	Console.WriteLine(string.Join(" ", selectionSorted));
	Console.WriteLine(IsStable(c, selectionSorted ) ? "Stable" : "Not stable");
}
public static string[] BubbleSort(string[] cparam, int n)
{
	var c = (string[])cparam.Clone();
	for (var i = 0; i < n - 1; i++)
		for (var j = n - 1; j > i; j--)
			if (int.Parse(c[j].Substring(1)) < int.Parse(c[j - 1].Substring(1)))
			{
				var temp = c[j];
				c[j] = c[j - 1];
				c[j - 1] = temp;
			}
	
	return c;
}
public static string[] SelectionSort(string[] cparam, int n)
{
	var c = (string[])cparam.Clone();
	for (var i = 0; i < n - 1; i++)
	{
		var minj = i;
		for (var j = i; j < n; j++)
			if (int.Parse(c[j].Substring(1)) < int.Parse(c[minj].Substring(1)))
				minj = j;
		
		var temp = c[i];
		c[i] = c[minj];
		c[minj] = temp;
	}
	return c;
}
public static bool IsStable(string[] origin, string[] sorted)
{
	// 数字が同じものでまとめる
	var g = origin.GroupBy(x => int.Parse(x.Substring(1)));
	
	// 数字が同じものがあるもののみ
	foreach(var numberToInputs in g.Where(x => x.Count() > 1))
	{
		// ひとつ前のindexを保持
		var preIndex = -1;
		foreach (var input in numberToInputs)
		{
			// originの順番でsort済みのもののインデックス取得
			// sortedのインデックスが昇順でなかったらnot stable
			var index = Array.IndexOf(sorted, input);
			if (preIndex > index)
				return false;
			preIndex = index;
		}
	}
	
	return true;
}