using System;
using System.Collections;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;

namespace csharp
{
	class CArray {
		private int[] arr;
		private int upper;
		private int numElements;
		private  int size;
		
		public CArray(int sz) {
			this.size = sz;
			arr = new int[size];
			upper = size-1;
			numElements = 0;
		}
		
		public void Insert(int item) {
			arr[numElements] = item;
			numElements++;
		}
		
		public void DisplayElements() {
			for(int i = 0; i <= upper; i++) {
				Console.Write(arr[i] + " ");
			}
			Console.WriteLine();
		}
		
		public void Clear() {
			for(int i = 0; i <= upper; i++) {
				arr[i] = 0;
				numElements = 0;
			}
		}
		
		public void BubbleSort() {
			int temp;
			 for (int outer = 0; outer < size; outer++)
            {
                for (int inner = 0; inner < outer; inner++)
                {
                    if (arr[outer] < arr[inner])
                    {
                        temp = arr[outer];
                        arr[outer] = arr[inner];
                        arr[inner] = temp;
                    }
					//this.DisplayElements();
                }
            }
		}
		
		public void SelectionSort() {
			int min, temp;
			for(int outer = 0; outer <= upper; outer++) {
				min = outer;
				for(int inner = outer + 1; inner <= upper; inner++) {
					if (arr[inner] < arr[min])
						min = inner;
				}
				temp = arr[outer];
				arr[outer] = arr[min];
				arr[min] = temp;
				//this.DisplayElements();
			}
		}
		
		public void InsertionSort() {
			int inner, temp;
			for(int outer = 1; outer <= upper; outer++) {
				temp = arr[outer];
				inner = outer;
				while (inner > 0 && arr[inner-1] >= temp) {
					arr[inner] = arr[inner-1];
					inner--;
				}
				arr[inner] = temp;
				//this.DisplayElements();
			}
		}
	}
	
    class chapter2
    {
        static void Main(string[] args)
        {
			const int size = 10000;
			CArray nums = new CArray(size);
			Random rnd = new Random(100);
			Stopwatch watch = new Stopwatch();
			for(int i = 0; i < size; i++) {
				nums.Insert(rnd.Next(1,100));
			}
			watch.Start();
			nums.SelectionSort();
			watch.Stop();
			TimeSpan ts = watch.Elapsed;
			int elapsedTime = ts.Milliseconds;
			Console.WriteLine("Time for selection sort (in milliseconds): " + elapsedTime);
			nums.Clear();
			for(int i = 0; i < size; i++) {
				nums.Insert(rnd.Next(1,100));
			}
			watch.Start();
			nums.BubbleSort();
			watch.Stop();
			ts = watch.Elapsed;
			elapsedTime = ts.Milliseconds;
			Console.WriteLine("Time for bubble sort (in milliseconds): " + elapsedTime);
			nums.Clear();
			for(int i = 0; i < size; i++) {
				nums.Insert(rnd.Next(1,100));
			}
			watch.Start();
			nums.InsertionSort();
			watch.Stop();
			ts = watch.Elapsed;
			elapsedTime = ts.Milliseconds;
			Console.WriteLine("Time for insertion sort (in milliseconds): " + elapsedTime);
			Console.ReadKey();
        }
    }
}