Functions

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iterator>
#include <iostream>
#include <time.h>

using namespace std;
float execTime;
int addComparation;
int addSwitch;



int vectorSize(int vector[]){
	return (sizeof(vector)/sizeof(int));
}


void show(int vetor[], int el){

	 for(int j = 0; j < el; j++){
	 	printf("%d,", vetor[j]);
	 }
}

void shellSort(int vet[], int size) {
    int i , j , value;
    int gap = 1;
    addComparation ++;
    while(gap < size) {
    	addComparation ++;
        gap = 3*gap+1;
    }
   	addComparation ++;
    while ( gap > 1) {
    	addComparation ++;
        gap /= 3;
        for(i = gap; i < size; i++) {
        	addComparation ++;
            value = vet[i];
            j = i - gap;
            addComparation ++;
            while (j >= 0 && value < vet[j]) {
            	addComparation ++;
                vet [j + gap] = vet[j];
                 addSwitch ++;
                j -= gap;
            }
            vet [j + gap] = value;
             addSwitch ++;
        }
    }
}


void heapsort(int a[], int n) {

   int i = n / 2, pai, filho, t;

   for (;;) {
   		addComparation ++;
      if (i > 0) {
          i--;
          t = a[i];
      } else {
          n--;
          	addComparation ++;
          if (n == 0) return;
          t = a[n];
          a[n] = a[0];
          addSwitch ++;
      }

      pai = i;

      //Primeiro será feita a comparação com o filho da esquerda.
      filho = i * 2 + 1;
	  addComparation ++;
      while (filho < n) {
		 addComparation ++;
         //Se o filho da esquerda for menor do que o filho da direita,então será feita a troca do filho que será comparado.
          addComparation ++;
          if ((filho + 1 < n)  &&  (a[filho + 1] > a[filho])){
              filho++;
          }
          addComparation ++;
          if (a[filho] > t) {
             a[pai] = a[filho];
              addSwitch ++;
             pai = filho;
             filho = pai * 2 + 1;
          } else {
             break;
          }
      }
      a[pai] = t;
       addSwitch ++;
   }
}


void mergeSort(int *vetor, int posicaoInicio, int posicaoFim) {
    int i, j, k, metadeTamanho, *vetorTemp;

    if(posicaoInicio == posicaoFim) return;

    // ordenacao recursiva das duas metades
    metadeTamanho = (posicaoInicio + posicaoFim ) / 2;
    mergeSort(vetor, posicaoInicio, metadeTamanho);
    mergeSort(vetor, metadeTamanho + 1, posicaoFim);

    // intercalacao no vetor temporario t
    i = posicaoInicio;
    j = metadeTamanho + 1;
    k = 0;
    vetorTemp = (int *) malloc(sizeof(int) * (posicaoFim - posicaoInicio + 1));
	addComparation ++;
    while(i < metadeTamanho + 1 || j  < posicaoFim + 1) {
    	addComparation ++;
        if (i == metadeTamanho + 1 ) { // i passou do final da primeira metade, pegar v[j]
           	addSwitch ++;
		    vetorTemp[k] = vetor[j];
            j++;
            k++;
        }
        else {
        		addComparation ++;
            if (j == posicaoFim + 1) { // j passou do final da segunda metade, pegar v[i]
                addSwitch ++;
				vetorTemp[k] = vetor[i];
                i++;
                k++;
            }
            else {
            		addComparation ++;
                if (vetor[i] < vetor[j]) {
                    addSwitch ++;
					vetorTemp[k] = vetor[i];
                    i++;
                    k++;
                }
                else {
                    addSwitch ++;
					vetorTemp[k] = vetor[j];
                    j++;
                    k++;
                }
            }
        }

    }
    // copia vetor intercalado para o vetor original
    for(i = posicaoInicio; i <= posicaoFim; i++) {
    	addSwitch ++;
        vetor[i] = vetorTemp[i - posicaoInicio];
    }
    free(vetorTemp);
}

void quickSort(int valor[], int esquerda, int direita)
{
    int i, j, x, y;
    i = esquerda;
    j = direita;
    x = valor[(esquerda + direita) / 2];

	addComparation ++;
    while(i <= j)
    {
    	addComparation ++;
        while(valor[i] < x && i < direita)
        {
        	addComparation ++;
            i++;
        }
        while(valor[j] > x && j > esquerda)
        {
        	addComparation ++;
            j--;
        }
        if(i <= j)
        {
        	addComparation ++;
        	addSwitch ++;
            y = valor[i];
            valor[i] = valor[j];
            valor[j] = y;
            i++;
            j--;
        }
    }
    if(j > esquerda)
    {
    	addComparation ++;
        quickSort(valor, esquerda, j);
    }
    if(i < direita)
    {
    	addComparation ++;
        quickSort(valor,  i, direita);
    }
}

void bubbleSort(int vetor[], int el){
	for(int i=el-1; i >= 1; i--) {

	    for( int j=0; j < i ; j++) {
	      addComparation ++;
	      if(vetor[j]>vetor[j+1]) {
	        addSwitch ++;
	        int aux = vetor[j];
	        vetor[j] = vetor[j+1];
	        vetor[j+1] = aux;

	    	}
	    }
    }
}

void insertionSort(int vetor[], int el){
   int j,i,key;
   for(j = 1; j < el; j++){
      key = vetor[j];
      i = j - 1;
      addComparation ++;
      while(i >= 0 && vetor[i] > key){
      	 addComparation ++;
         vetor[i + 1] = vetor[i];
         addSwitch ++;
         i = i - 1;
      }
      vetor[i + 1] = key;
      addSwitch ++;
   }
}

int main(){



  int numElementos;

    printf("Insira a quantidade de elementos do vetor: ");
    scanf("%i", &numElementos);

    int vet[numElementos];

    for(int i = 0; i < numElementos; i++) {

        vet[i] = rand() % numElementos + 1;

    }

	int el = sizeof(vet)/sizeof(int);

	addComparation = 0;
	addSwitch = 0;
	clock_t tStart = clock(); // INICIA RELOGIO
	shellSort(vet,el);
	printf("Time taken: %fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
	printf("Switch %d, Comparations %d\n\n\n\n",addSwitch,addComparation);
	//show(vet,el);




}