#include <iostream>
#include<stdio.h>
#include <string.h>
#include <time.h>
#define total_repet  560
#define classes  4
#define arquivos  15
#define metodos  7
using namespace std;
#include "MetodosAss2.h"
#include "Metodos2.cpp"


Resul resul[total_repet];

int Maior(int vet[], int tam){
  int maior = -1;

  for(int i=0; i<tam; i++){
    if(vet[i] > maior){
      maior = vet[i];
    }
  }
  return maior;
}


int main()
{
    FILE *arq;
    FILE *pont_arq;
    char nomeArq[20];
    int numero[20] = {100,200,500,1000,2000,5000,7500,10000,15000,30000,50000,75000,100000,200000,500000,750000,1000000,1250000,1500000,2000000};
    int tam = 0, lixo, aux, contador = 0 ;

    for(int k=0;k<classes;k++){
        for(int j=0; j<arquivos; j++){
                if(k==0){
                  snprintf (nomeArq, sizeof(nomeArq), "a%d.txt", numero[j]);
                }
                if(k==1){
                   snprintf (nomeArq, sizeof(nomeArq), "d%d.txt", numero[j]);
                }
                if(k==2){
                    snprintf (nomeArq, sizeof(nomeArq), "o%d.txt", numero[j]);
                }
                if(k==3){
                    snprintf (nomeArq, sizeof(nomeArq), "po%d.txt", numero[j]);
                }
                printf("nome arq: %s \n", nomeArq);
                arq = fopen(nomeArq, "r");
                while(fscanf(arq,"%d", &lixo) != EOF){
                    tam++;
                }
                rewind(arq);
                int vet[tam], i=0, vetauxiliar[tam];
                int comeco=0, fim = tam-1, maior=0;
                while (fscanf(arq,"%d", &aux) != EOF){
                    vet[i] = aux;
                    i++;
                }

                for(int cont=0; cont<tam; cont++){
                  vetauxiliar[cont] = vet[cont];
                }

                for(int alg=0;alg<metodos;alg++){
                    for(int cont=0; cont<tam; cont++){
                       vet[cont] = vetauxiliar[cont];
                    }

                    strcpy(resul[contador].Nome_arq, nomeArq);
                    if(alg==0){
                        bubble_sort(vet,tam,contador,resul);
                        strcpy(resul[contador].metodo, "bubble_sort");
                        pont_arq = fopen("C:\\Users\\Fernando-\\Dropbox\\Trabalhos\\PAA\\TrabalhoPAA\\bubbleResul.txt", "a");
                        fprintf(pont_arq, "%s %lld %lld %f \n", resul[contador].Nome_arq, resul[contador].swaps, resul[contador].compara, resul[contador].tempo );
                    }
                    if(alg==1){
                        Insertion_sort(vet,tam,contador,resul);
                        strcpy(resul[contador].metodo, "Insertion_sort");
                        pont_arq = fopen("C:\\Users\\Fernando-\\Dropbox\\Trabalhos\\PAA\\TrabalhoPAA\\InsertionResul.txt", "a");
                        fprintf(pont_arq, "%s %lld %lld %f \n", resul[contador].Nome_arq, resul[contador].swaps, resul[contador].compara, resul[contador].tempo );
                    }
                    if(alg==2){
                        Selection_sort(vet,tam,contador,resul);
                        strcpy(resul[contador].metodo, "Selection_sort");
                        pont_arq = fopen("C:\\Users\\Fernando-\\Dropbox\\Trabalhos\\PAA\\TrabalhoPAA\\SelectionResul.txt", "a");
                        fprintf(pont_arq, "%s %lld %lld %f \n", resul[contador].Nome_arq, resul[contador].swaps, resul[contador].compara, resul[contador].tempo );
                    }
                    if(alg==3){
                        Merge_sort(vet,tam,contador,resul,comeco);
                        strcpy(resul[contador].metodo, "Merge_sort");
                        pont_arq = fopen("C:\\Users\\Fernando-\\Dropbox\\Trabalhos\\PAA\\TrabalhoPAA\\MergeResul.txt", "a");
                        fprintf(pont_arq, "%s %lld %lld %f \n", resul[contador].Nome_arq, resul[contador].swaps, resul[contador].compara, resul[contador].tempo );
                    }
                    if(alg==4){
                        quicksort(vet,comeco,tam,resul,contador);
                        strcpy(resul[contador].metodo, "Quick_sort");
                        pont_arq = fopen("C:\\Users\\Fernando-\\Dropbox\\Trabalhos\\PAA\\TrabalhoPAA\\QuickResul.txt", "a");
                        fprintf(pont_arq, "%s %lld %lld %f \n", resul[contador].Nome_arq, resul[contador].swaps, resul[contador].compara, resul[contador].tempo );
                    }
                    if(alg==5){
                        maior = Maior(vet,tam);
                        Counting_sort(vet,tam,contador,maior,resul);
                        strcpy(resul[contador].metodo, "Countting_sort");
                        pont_arq = fopen("C:\\Users\\Fernando-\\Dropbox\\Trabalhos\\PAA\\TrabalhoPAA\\CounttingResul.txt", "a");
                        fprintf(pont_arq, "%s %lld %lld %f \n", resul[contador].Nome_arq, resul[contador].swaps, resul[contador].compara, resul[contador].tempo );
                    }
                    if(alg==6){
                        printf("entrou\n");
                        Bucket_sort(vet,tam,contador,resul);
                        strcpy(resul[contador].metodo, "Bucket_sort");
                        pont_arq = fopen("C:\\Users\\Fernando-\\Dropbox\\Trabalhos\\PAA\\TrabalhoPAA\\BucketResul.txt", "a");
                        fprintf(pont_arq, "%s %lld %lld %f \n", resul[contador].Nome_arq, resul[contador].swaps, resul[contador].compara, resul[contador].tempo );
                        printf("saiu\n");
                    }
                    //printf("resul[contador].metodo %s \t contador = %d \n", resul[contador].metodo, contador);
                    contador++;
            }
            tam= 0;
        }
    }
    fclose(arq);
    fclose(pont_arq);

    return 0;
}

/////////////////////////////////////////////////
#include "MetodosAss2.h"
#include <iostream>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;

void Selection_sort(int vetor[], int n, int contador,  Resul *x) {

    long long int k, swaps = 0 , compara=0, indiceMenor;
    time_t t_ini , t_fim;
    t_ini = time(NULL);
    for (k = 0; k < n; ++k) {
      indiceMenor = k;
        for (long long int indiceSeguinte = k+1; indiceSeguinte < n; ++indiceSeguinte) {
            compara++;
            if (vetor[indiceSeguinte] < vetor[indiceMenor]) {
                indiceMenor = indiceSeguinte;
            }
        }
        swaps++;
        long long int aux = vetor[k];
        vetor[k] = vetor[indiceMenor];
        vetor[indiceMenor] = aux;
    }
    t_fim = time(NULL);
    x[contador].tempo = difftime(t_ini,t_fim);
    x[contador].swaps = swaps;
    x[contador].compara = compara;
}

void Quick_sort(int values[], int comeco, int fim, Resul *x,  int contador){
	long long int i, j, pivo, aux;
	long long int swaps = 0 , compara=0;

	i = comeco;
	j = fim-1;
	pivo = values[(comeco + fim) / 2];
	while(i <= j){
		while(values[i] < pivo && i < fim){
			compara++;
			i++;
		}
		while(values[j] > pivo && j > comeco){
			compara++;
			j--;
		}
		swaps++;
		if(i <= j){
			aux = values[i];
			values[i] = values[j];
			values[j] = aux;
			i++;
			j--;
		}
	}
	if(j > comeco)
		Quick_sort(values, comeco, j+1, x, contador);
	if(i < fim)
		Quick_sort(values, i, fim, x, contador);

	x[contador].compara = compara;
	x[contador].swaps = swaps;
}

void quicksort(int values[], int comeco, int fim, Resul *x, int contador)
{
	time_t t_ini , t_fim;
	t_ini = time(NULL);
	Quick_sort(values, comeco, fim, x, contador);
	t_fim = time(NULL);
	x[contador].tempo = difftime(t_ini,t_fim);
}

int merge(int vetor[], int comeco, int meio, int fim) {

    long long int compara=0, indiceMenor;
    time_t t_ini , t_fim;
    long long int com1 = comeco, com2 = meio+1, comAux = 0, tam = fim-comeco+1;
    long long int *vetAux;
    vetAux = (long long int*)malloc(tam * sizeof(long long int));

    while(com1 <= meio && com2 <= fim){
      compara++;
      if(vetor[com1] < vetor[com2]) {
        vetAux[comAux] = vetor[com1];
        com1++;
      } else {
        vetAux[comAux] = vetor[com2];
        com2++;
      }
      comAux++;
    }

    while(com1 <= meio){  //Caso ainda haja elementos na primeira metade
      vetAux[comAux] = vetor[com1];
      comAux++;
      com1++;
    }

    while(com2 <= fim) {   //Caso ainda haja elementos na segunda metade
      vetAux[comAux] = vetor[com2];
      comAux++;
      com2++;
    }

    for(comAux = comeco; comAux <= fim; comAux++){    //Move os elementos de volta para o vetor original
      vetor[comAux] = vetAux[comAux-comeco];
    }
    free(vetAux);
    return compara;
}

void Merge_sort(int vetor[], int fim, int contador,  Resul *x, int comeco){
    long long int swaps=0 , compara=0;
    time_t t_ini , t_fim;
    t_ini = time(NULL);
    if(comeco < fim){
        int meio = (comeco + fim) / 2;
        Merge_sort(vetor, meio, contador, x, comeco);
        Merge_sort(vetor, fim, contador, x, meio+1);
        compara = merge(vetor, comeco, meio, fim);
    }
    t_fim = time(NULL);
    x[contador].tempo = difftime(t_ini,t_fim);
    x[contador].swaps = swaps;
    x[contador].compara = compara;
}

void Insertion_sort(int vetor[], int n, int contador,  Resul *x) {

    long long int k, j, aux, swaps = 0 , compara=0, escolhido;
    time_t t_ini , t_fim;
    t_ini = time(NULL);
    for (k = 1; k < n; k++){
      escolhido = vetor[k];
      j = k - 1;
      while ((j >= 0) && (vetor[j] > escolhido)) {
        compara++;
        swaps++;
        vetor[j+1] = vetor[j];
        j--;
      }
      compara++;
      swaps++;
      vetor[j+1] = escolhido;
    }
    t_fim = time(NULL);
    x[contador].tempo = difftime(t_ini,t_fim);
    x[contador].swaps = swaps;
    x[contador].compara = compara;
}

void Counting_sort(int values[], int tam, int contador, int maior, Resul *x){

  long long int i, j;
  long long int C[maior+1], B[tam];
  long long int swaps = 0 , compara=0;
  time_t t_ini , t_fim;


  t_ini = time(NULL);

  for (i=0; i<=maior; i++)
        C[i]=0;

  for (j=0; j<tam; j++)
        C[values[j]] = C[values[j]] + 1;

  for (i=1; i<maior; i++)
        C[i] = C[i] + C[i-1];

  for (j=tam-1; j>=0; j--){
        B[C[values[j]]-1] = values[j];
        C[values[j]] = C[values[j]]-1;
  }
  t_fim = time(NULL);
  x[contador].tempo = difftime(t_ini,t_fim);
  x[contador].swaps = swaps;
  x[contador].compara = compara;

}

void bubble_sort(int vetor[], int n, int contador, Resul *x) {

    long int k, j, aux ;
    long long int swaps = 0, compara=0;
    float tempo = 0;
    time_t t_ini , t_fim;
    time(&t_ini);
    for (k = 1; k < n; k++) {
        for (j = 0; j < n - 1; j++) {
            compara++;
            if (vetor[j] > vetor[j + 1]) {
                swaps++;
                //printf("swap = %ld \n", swaps);
                aux = vetor[j];
                vetor[j] = vetor[j+1];
                vetor[j+1] = aux;
            }
        }
    }
    time(&t_fim);
    float tempo_bub = difftime(t_fim, t_ini);

    x[contador].tempo = tempo_bub;
    x[contador].swaps = swaps;
    x[contador].compara = compara;

}


struct bucket
{
    int count;
    int* value;
};

int compareIntegers(const void* first, const void* second)
{
    int x = *((int*)first), y =  *((int*)second);
    if (x == y)
    {
        return 0;
    }
    else if (x < y)
    {
        return -1;
    }
    else
    {
        return 1;
    }
}
void Bucket_sort(int array[], int n, int contador, Resul *x){

  time_t t_ini,t_fim;
  long long int swaps=0, compara=0;


    struct bucket buckets[3];
    int i, j, k;
    t_ini = time(NULL);
    for (i = 0; i < 3; i++){
        buckets[i].count = 0;
        buckets[i].value = (int*)malloc(sizeof(int) * n);
    }
    for (i = 0; i < n; i++){
        compara += 2;
        if (array[i] < 0)
        {
            buckets[0].value[buckets[0].count++] = array[i];
        }
        else if (array[i] > 10){
            buckets[2].value[buckets[2].count++] = array[i];
        }
        else
        {
            buckets[1].value[buckets[1].count++] = array[i];
        }
    }
    for (k = 0, i = 0; i < 3; i++){
        // now using quicksort to sort the elements of buckets
        qsort(buckets[i].value, buckets[i].count, sizeof(int), &compareIntegers);
        for (j = 0; j < buckets[i].count; j++){
            array[k + j] = buckets[i].value[j];
        }
        k += buckets[i].count;
        free(buckets[i].value);
    }


  t_fim = time(NULL);

  x[contador].tempo = difftime(t_ini,t_fim);
  x[contador].swaps = swaps;
  x[contador].compara = compara;

}



//////////////////////////////
#ifndef METODOSASS
#define METODOSASS

struct Resultados{

    char metodo[500];
    char Nome_arq[500];
    long long int swaps;
    long long int compara;
    float tempo;
};
typedef struct Resultados Resul;

void Bucket_sort(int values[], int tam, int contador,  Resul *x);
void Counting_sort(int values[], int tam, int contador, int maior,  Resul *x);
void Insertion_sort(int vetor[], int n, int contador,  Resul *x);
void Merge_sort(int vetor[], int fim, int contador,  Resul *x, int comeco);
void bubble_sort(int vetor[], int n, int contador,  Resul *x);
void quicksort(int values[], int comeco, int fim,  Resul *x,  int contador);
void Selection_sort(int vetor[], int n, int contador,  Resul *x);

#endif