#include<iostream>
#include<time.h>
#define N 100000
using namespace std;
void kiir(int a[], int n);
void InsertionSort(int a[], int n);
void SelectionSort(int a[], int n);

void main() {
	int a[N], v;
	cout << "Best case(1) / Worst Case(2)\n";
	cin >> v;
	clock_t start, stop;
	switch (v) {
	case 1: {
		for (int i = 0; i < N; ++i) {
			a[i] = i;
		}
		break;
	}
	case 2: {
		for (int i = 0; i < N; ++i) {
			a[i] = N - i - 1;
		}
		break;
	}
	}
	int r;
	cout << "\n1.Insertion Sort\n2.Selection sort\n";
	cin >> r;
	switch (r) {
	case 1: {
		start = clock();
		InsertionSort(a, N);
		stop = clock();
		break;
		}
	case 2: {
		start = clock();
		SelectionSort(a, N);
		stop = clock();
		}
	}
	kiir(a, N);
	double ido = stop - start;
	ido /= CLOCKS_PER_SEC;
	cout << ido;
}

void kiir(int a[], int n) {
	int i;
	for (i = 0; i < n; ++i) {
		cout << a[i] << " ";
	}
	cout << endl;
}
void InsertionSort(int a[], int n) {
	int i, k, j;
	for (i = 1; i < n; ++i) {
		k = a[i];
		j = i - 1;
		while (j >= 0 && a[j] > k) {
			a[j + 1] = a[j];
			--j;
		}
		a[j + 1] = k;
	}
}
void SelectionSort(int a[], int n) {
	int i, j, k;
	for (i = 0; i < N - 1; ++i) {
		k = i;
		for (j = i + 1; j < n; ++j)
		if (a[j] < a[k])
				k = j;
		int temp = a[k];
		a[k] = a[i];
		a[i] = temp;
	}
}