#include <stdio.h>
#include <stdlib.h>

int u[] = {12,44,03,42,06,55,94,67};
int w[] = {1,3,5,72,4,6,8,9,10};
int sizeu = 8;
int sizew = 10;

void imprimir(int *v, int n);

void troca(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;

}

void quickSort(int *v, int n){

    int i, j, pivo;

    if (n<=1) return;

    pivo = v[0];
    i=1;
    j=n-1;

    do{
        while (i<n && v[i]<=pivo) i++;

        while (v[j]>pivo) j--;

        if(i<j){
            troca(&v[i],&v[j]);
            i++;
            j--;
        }


    }while (i<=j);

    v[0] = v[j];
    v[j] = pivo;

    imprimir(u,sizeu);

    quickSort(v,j);
    quickSort(&v[i],n-i);

}

void imprimir(int *v, int n){

    for (int i=0;i<n;i++){
        printf("%d ",v[i]);
    }

    printf("\n");

}

void merge(int *v, int ini_esq, int fim_esq, int ini_dir, int fim_dir){

    int temp[100];
    int i = ini_esq;
    int j = ini_dir;
    int k = 0;

    while (i<=fim_esq && j<=fim_dir){
        if (v[i]<v[j])
            temp[k++] = v[i++];
        else
            temp[k++] = v[j++];
    }

    while (i<=fim_esq){
        temp[k++] = v[i++];
    }

    while (j<=fim_dir){
        temp[k++] = v[j++];
    }

    for(i=ini_esq,j=0;i<=fim_dir;i++,j++)
        v[j] = temp[i];

    imprimir(temp,fim_dir);


}


void mergeSort(int *v, int ini, int fim){
    int meio;

    if (ini<fim){

        meio = (ini + fim)/2;

        mergeSort(v,ini,meio-1);
        mergeSort(v,meio,fim);

        merge(v,ini,meio-1,meio, fim);
    }

}

int main()
{
    printf("QuickSort\n");

    printf("Original\n");
    imprimir(u,sizeu);
    printf("\n");
    quickSort(u,sizeu);
    printf("\nOrdenado\n");
    imprimir(u,sizeu);
    printf("\n");

    printf("MergeSort\n");
    imprimir(w,sizew);
    printf("\n");
    //mergeSort(w,0,sizew-1);
    merge(w,0,3,4,9);
    printf("\nOrdenado\n");
    imprimir(w,sizew);


    return 0;
}
