void insertionSort(int *vetor, int lenght)
{
    int i,j,atual;
    for(i=0; i<lenght; i++)
    {
        atual = vetor[i];
        j = i-1;

        while((j>=0)&&(atual<vetor[j]))
        {
            vetor[j + 1] = vetor[j];
            j = j-1;
        }
        vetor[j+1] = atual;
    }
}
void merge(int vetor[], int comeco, int meio, int fim)
{
    int com1 = comeco, com2 = meio+1, comAux = 0;
    int vetAux[fim-comeco+1];
    while(com1<=meio && com2<=fim)
    {
        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];
    }
}
void mergeSort(int vetor[], int comeco, int fim)
{
    if (comeco < fim)
    {
        int meio = (comeco+fim)/2;
        mergeSort(vetor, comeco, meio);
        mergeSort(vetor, meio+1, fim);
        merge(vetor, comeco, meio, fim);
    }
}
void maxHeapfy(int vetor[],int lenght,int x){
    int maior = x;
    int aux;
    if(x*2 <= lenght && vetor[x*2]>vetor[maior])maior = x*2;
    if(x*2+1 <= lenght && vetor[x*2+1]>vetor[maior])maior = x*2+1;
    if(maior != x){
        aux = vetor[x];
        vetor[x] = vetor[maior];
        vetor[maior] = aux;
        maxHeapfy(vetor,lenght,maior);
    }
}
void constroiHeap(int vetor[],int lenght){
    int i;
    for(i=lenght/2;i>=0;i--) maxHeapfy(vetor,lenght,i);
}
void heapSort(int vetor[], int lenght){
    int i,aux;
    constroiHeap(vetor,lenght);
    for(i=lenght;i>0;i--){
        aux = vetor[0];
        vetor[0] = vetor[i];
        vetor[i] = aux;
        maxHeapfy(vetor,i-1,0);
    }
}
void quickSort(int vetor[], int inicio, int fim)
{

    int pivo, aux, i, j, meio;

    i = inicio;
    j = fim;

    meio = (int) ((i + j) / 2);
    pivo = vetor[meio];

    do
    {
        while (vetor[i] < pivo) i = i + 1;
        while (vetor[j] > pivo) j = j - 1;

        if(i <= j)
        {
            aux = vetor[i];
            vetor[i] = vetor[j];
            vetor[j] = aux;
            i = i + 1;
            j = j - 1;
        }
    }
    while(j > i);

    if(inicio < j) quickSort(vetor, inicio, j);
    if(i < fim) quickSort(vetor, i, fim);

}
countSort(int vetor[],int length,int range)
{
    int *count,i;
    int *aux;
    aux = (int*)malloc(length*sizeof(int));
    count =  (int*)malloc(range*sizeof(int));
    for(i=0; i<range; i++)count[i]=0;
    for(i=0; i<length; i++)count[vetor[i]]++;
    for(i=1; i<range; i++)count[i] +=count[i-1];
    for(i=0; i<length; i++)
    {
        aux[count[vetor[i]]-1] = vetor[i];
        count[vetor[i]]--;
    }
    for(i=0; i<length; i++)
    {
        vetor[i] = aux[i];
    }
    free(count);
    free(aux);
}
void radixSort(int vetor[], int tamanho)
{
    int i;
    int *VetOrdenado;
    int maior = vetor[0];
    int exp = 1;

    VetOrdenado = (int *)calloc(tamanho, sizeof(int));

    for (i = 0; i < tamanho; i++)
    {
        if (vetor[i] > maior)
            maior = vetor[i];
    }

    while (maior/exp > 0)
    {
        int aux[10] = { 0 };
        for (i = 0; i < tamanho; i++)
            aux[(vetor[i] / exp) % 10]++;
        for (i = 1; i < 10; i++)
            aux[i] += aux[i - 1];
        for (i = tamanho - 1; i >= 0; i--)
            VetOrdenado[--aux[(vetor[i] / exp) % 10]] = vetor[i];
        for (i = 0; i < tamanho; i++)
            vetor[i] = VetOrdenado[i];
        exp *= 10;
    }

    free(VetOrdenado);
}