Estrutura de Dados e Algoritmos II - Métodos de Ordenação

Estrutura de Dados e Projetos de Algoritmos

Máquina utilizada: Intel i7 2.4GHz - 8GB de RAM - Windows 10 64bits

Objetivo: Implementar os algoritmos BubbleSort, QuickSort, HeapSort e MergeSort e efetuar a análise empírica para entradas de 15000, 75000, 295000 e 2500000.

Resultados:

------------------------	15000	75000	295000	2500000
BubbleSort	0.594s	16.384s	4m 12s	5h 49m 28s
QuickSort	0.003s	0.13s	0.058s	0.0716
HeapSort	0.00s	0.021s	0.112s	1.193s
MergeSort	0.01s	0.02s	0.1s	0.84s

Com os resultados obtidos, podemos perceber que existe uma grande diferença de tempo, em especial para valores muito grandes, entre os algoritmos de complexidade O(n²) (BubbleSort) para os de complexidade Θ (n log n) (QuickSort, HeapSort, MergeSort), ambos no caso médio.

Para o teste, foram gerados números aleatórios, variando entre zero e o dobro do número de entradas.

        Segue abaixo os códigos:

Bubble Sort

#include

#include[pic 1]

#include

int a;

void ord_bolha (int *v, int tam){

    int i,j, aux;

    typedef int bool;

    enum { false, true };

    bool ordenado;

    for(i=0;i

            ordenado = true;

        for(j=0;j

            if(v[j] > v[j+1]){

                aux = v[j];

                v[j] = v[j+1];

                v[j+1] = aux;

                ordenado = false;

            }

        }

        if (ordenado==true)

            break;

    }

}

void main(a){

    int tam_a;

    printf("BubbleSort\n");

    for (a=1;a<=4;a++){

    switch(a){

    case 1:

        tam_a = 2500000;

        executa(tam_a);

        break;

    case 2:

        tam_a = 75000;

        executa(tam_a);

        break;

    case 3:

        tam_a = 295000;

        executa(tam_a);

        break;

    case 4:

        tam_a = 15000;

        executa(tam_a);

        break;

    default:

        tam_a = 0;

        system("PAUSE");

        break;

    }

}

}

void executa(int tam_a){

clock_t start, end;

    double cpu_time_used;

    start = clock();

    int t;

    int *v;

    free(v);

    v=(int *) malloc(tam_a*sizeof(int));

    if (v==NULL) {

        printf("Error");

    }

    srand(time(NULL));

    for(t=0;t

        int r = rand()%(tam_a*2);

        v[t] = r;

    }

    printf("Tamanho do array: %d\n", tam_a);

    ord_bolha(v, tam_a);

    end = clock();

    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

    printf("Tempo: %f\n\n", cpu_time_used);

}

void exibe_numeros(int *v, int tam_a){

    int f;

    printf("\nNumeros ordenados: \n");

    for(f=0;f