#include "stdafx.h"
#include <string.h>
#include <conio.h>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <thread>
#include <chrono>


using namespace std;


//llena toda la cadena con numeros random
void fill(int array[], int N, int min, int max)
{
	srand(time(NULL));

	for (int i = 0; i<N; i++)
	{
		array[i] = (rand() % (max - min)) + min;
	}
}

//hace los cambios de un lugar a otro
void swap(int &a, int &b)
{

	int temp = a;
	a = b;
	b = temp;
}



//realiza el algoritmo de inserción
void insertion(int array[], int N, int *cambios, int* comparaciones)
{

	for (int i = 1; i < N; i++) {
		for (int x = i - 1; x >= 0; x--) {
			(*comparaciones)++;
			if (array[x + 1] < array[x]) {
				swap(array[x + 1], array[x]);
				(*cambios)++;
			}
			else {
				break;
			}
		}
	}

}

//ordenamiento shell
void shell(int array[], int N, int *cambios, int* comparaciones)
{
	//el ciclo se hara hasta que h==0
	for (int h = N / 2; h != 0; h /= 2) {
		bool noCambios = true;
		//si no hubo cambios en la esa fase, el ciclo se cierra.
		while (noCambios)
		{
			noCambios = false;
			//este ciclo se hace antes de que se llegue a aun desbordamiento
			for (int o = 0; o < h; o++)
			{
				for (int i = o; i + h < N; i += h)
				{
					(*comparaciones)++;
					if (array[i] > array[i + h]) {
						//se realizan los cambios de lugar
						swap(array[i], array[i + h]);
						(*cambios)++;
						if (i - h >= 0) {
							i -= (2*h);
						}
						noCambios = true;

					}
				}
			}
		}
	}

}

int main()
{
	//tamaño del arreglo (se va modificando)
	int const x = 10;

	int totalcambiosS=0;
	int toatalcomparacionesS=0;
	int totalcambiosI = 0;
	int toatalcomparacionesI = 0;
	//hace el test de 10 pruebas
	for (int i = 0; i < 10; i++) {
		int array[x] = {};
		int array2[x] = {};
		//espera 1 segundo para que las cadenas tengan diferentes numeros en cada intento.
		std::this_thread::sleep_for(std::chrono::seconds(1));
		//llegna el arreglo
		fill(array, x, 0, 50);
		//copia el arreglo 1 en el 2
		for (int n = 0; n < x; n++) {
			array2[n] = array[n];
		}
		//se aplican los metodos
		insertion(array, x,&totalcambiosI,&toatalcomparacionesI);
		shell(array2, x, &totalcambiosS, &toatalcomparacionesS);
	}

	cout << "promedio comparaciones en insercion  " << ((float)toatalcomparacionesI/10) << endl;
	cout << "promedio cambios en insercion  " << ((float)totalcambiosI/10 )<< endl;
	cout << "promedio comparaciones en sell  " << ((float)toatalcomparacionesS / 10) << endl;
	cout << "promedio cambios en sell  " << ((float)totalcambiosS / 10) << endl;

	_getch();
    return 0;
}