using System;

abstract class BaseSort
{
	protected int[] data;
	
	public BaseSort(int[] newData)
	{
		data = newData;
	}
	
	public override string ToString()
	{
		string ret = "{ ";
		foreach (int num in data)
			ret += num + " ";
		ret += "}";
		return ret;
	}
	
	protected int Min (int index)
	{
		int min = index;
		for (int i=index; i<data.Length; i++)
		{
			if (data[i] <= data[min])
				min = i;
		}
		
		return min;
	}
	
	protected void Swap (int p1, int p2)
	{
		int tmp = data[p1];
		data[p1] = data[p2];
		data[p2] = tmp;
	}
	
	public abstract void Sort();
}

class InsertionSort : BaseSort
{
	public InsertionSort(int[] newData): base (newData){}
	
	public override void Sort()
	{
		for (int i=1; i<data.Length; i++)
		{
			int j;
			int tmp = data[i];
			
			for (j=i; j>0; j--)
			{
				if (data[j-1] > tmp)
				{
					data[j] = data[j-1];
				}
				else
				{
					break;
				}
			}
			data[j] = tmp;
		}
	}
}

class SelectionSort : BaseSort
{
	public SelectionSort(int[] newData): base (newData){}
	
	public override void Sort()
	{
		for (int i=0; i<data.Length; i++)
		{
			Swap(i, Min(i));
		}
	}
}

class BubbleSort : BaseSort
{
	public BubbleSort(int[] newData) : base (newData) {}
	
	public override void Sort ()
	{
		for (int i=0; i<data.Length; i++)
		{
			for (int j=i; j<data.Length; j++)
			{
				if (data[j] < data[i])
					Swap(i,j);
			}
		}
	}
}

class Program
{
	public static void Main ()
	{
		int[] data = {2, 5, 1, 2, 8, 34, -1};
		
		Console.WriteLine("Selection Sort:");
		SelectionSort ss = new SelectionSort(data);
		Console.WriteLine("Before: {0}", ss);
		ss.Sort();
		Console.WriteLine("After:  {0}", ss);
		
		int[] data2 = {2, 5, 1, 2, 8, 34, -1};
		Console.WriteLine("Insertion Sort:");
		InsertionSort ins = new InsertionSort(data2);
		Console.WriteLine("Before: {0}", ins);
		ins.Sort();
		Console.WriteLine("After:  {0}", ins);
		
		int[] data3 = {2, 5, 1, 2, 8, 34, -1};
		Console.WriteLine("BubbleSort");
		BubbleSort bs = new BubbleSort(data3);
		Console.WriteLine("Before: {0}", bs);
		bs.Sort();
		Console.WriteLine("After:  {0}", bs);
	}
}