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

int u[] = {12,44,03,42,06,55,94,67};
int w[] = {1,3,5,7,2,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 bubble_sort(int *v, int n){
    int i,j;

    for (i=n-1;i>0;i--){
        for(j=1;j<i;j++){
            if (v[j-1]>v[j]){
                troca(&v[j-1],&v[j]);
            }
            imprimir(u,sizeu);
        }
    }


}

void quick_sort(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);

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


}

void imprimir(int *v, int n){
    int i;

    for (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[i] = temp[j];

    imprimir(w,sizew);

}


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

    if (ini<fim){

        meio = (ini + fim)/2;

        merge_sort(v,ini,meio);
        merge_sort(v,meio+1,fim);

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

}

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

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


    printf("QuickSort\n");

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

    printf("MergeSort\n");
    imprimir(w,sizew);
    printf("\n");
    merge_sort(w,0,sizew-1);
    printf("\nOrdenado\n");
    imprimir(w,sizew);


    return 0;
}
