Algoritmos de ordenação lineares

ordenacao_linear.c

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

/* Definições */
#define BR printf("\n");
#define ALEATORIO 1
#define DECRESCENTE 2
#define CRESCENTE 3

#define TIPO_VETOR(n) n == 1?"Aleatório":n == 2?"Decrescente":"Crescente"

/* Globais */
unsigned long movimentos;     /* Contador de movimentos */


/* Protótipos para lista encadeada */
struct Nodo {
    int info;
    struct Nodo *prox;
};

typedef struct Nodo nodo;
nodo *criarLista();
void inserirLista(nodo *L,int info);
void destruirLista(nodo *L);
void selection(nodo *L);
/* Fim lista */

/* Protótipos */
/*void ordena(void (*sort)(int *,int),int *V,int n,char *nome,int tipoVetor);*/
void gerarVetor(int *vet, int tipoVet, int n);
void printV(FILE *saida,int *V,int n); 
void copy(int *V,int *C,int n);
int getMax(int *V,int n);
int getNumAlg(int num);

void countingSort(int *V,int n,int max);
void bucketSort(int *V, int n,int max); 
void radixSort(int *V, int n, int s);


void heapSort(int *V, int n);
void heapIfy(int *V, int n, int i);
void backHeap(int *V,int *C,int n);
void prepareHeap(int *V,int *C, int n);
 
void check(int *V,int n) {
    int i;
    for (i = 1;i < n;i++) {
        if (V[i] < V[i-1]) {
            printf("\nNão ordenou\n");
            return;
        }
    }
    printf("\nOrdenou o/ \n");
}
void *mallocX (unsigned int nbytes) 
{
   void *ptr;
   ptr = malloc (nbytes);
   if (ptr == NULL) {
      printf ("Erro! malloc devolveu NULL!\n");
      exit (EXIT_FAILURE);
   }
   return ptr;
}


int main(int argc, char **argv) {
    int n = 0,i;
    int tipoVetor = 0;
    int maior;
    int *vetor,*heap,*copia;
    FILE *saida;
        
    /* Validação simples para quantidade de argumento */ 
    if (argc != 3)  {
        printf("Erro de entrada.\n"
               "\tUse: ordena quantidade(n > 0) tipo(1,2,3)\n"
               "\tEx: ordena 1000 1\n");
        exit(1);
    }
    
    /* Pegando os valores da linha de comando*/
    n = atoi(argv[1]);
    tipoVetor = atoi(argv[2]);
    

    /* Alocando o vetor para ordenação e uma cópia. */
    vetor = (int *) mallocX(n * sizeof(int));
    copia = (int *) mallocX(n * sizeof(int));

    /* Gerando números para vetor */ 
    gerarVetor(vetor,tipoVetor,n);

    if (n < 100) { printV(stdout,vetor,n); BR }

    /* countingSort */   
    copy(copia,vetor,n);
    maior = getMax(copia,n);
    countingSort(copia,n,maior);
    check(copia,n);
    if (n < 100) { printV(stdout,copia,n); BR }

 

    /* BucketSort */ 
    copy(copia,vetor,n);
    maior = getMax(copia,n);
    bucketSort(copia,n,maior); 
    check(copia,n);
    if (n < 100) { printV(stdout,copia,n); BR }

    /* RadixSort */   
    copy(copia,vetor,n);
    maior = getNumAlg(getMax(copia,n));
    radixSort(copia,n,maior);
    check(copia,n);
    if (n < 100) { printV(stdout,copia,n); BR }


    /* HeapSort */
    heap = (int *) mallocX((n + 1) * sizeof(int));
    copy(copia,vetor,n);
    prepareHeap(copia,heap,n);
    heapSort(heap,n);
    backHeap(copia,heap,n);
    check(copia,n);
    if (n < 100) { printV(stdout,copia,n); BR }

    /* Liberando memória alocada */
    if (heap) free(heap);
    if (vetor) free(vetor);
    if (copia) free(copia);


    return 0;
}

/*
 * Imprime na tela o vetor V no formato [1,2,3,4,5,6]
 * int *V - Vetor de inteiros
 * int n - Tamanho do vetor
 */
void printV(FILE *saida,int *V,int n) {
    int i = 0;
    if (saida != NULL) 
       for (i = 0;i < n;i++)
           fprintf(saida,"%d ", V[i]);
}

/*
 * Copia o vetor C para o Vetor V
 * int *V - Vetor para onde vai a cópia
 * int *C - Vetor que vai ser copiado
 * int n - Tamanho dos vetores
 */
void copy(int *V,int *C,int n) {
    int i = 0;
    for (i = 0;i < n;i++)
        V[i] = C[i];
}

/* Calcula a quantidade de algarismo de um número
 * int num - Número para saber a qnt de algarismos
 * return int - Retorna a quantidade de algarismo do numero
 */
int getNumAlg(int num) {
    int c = 0;
    while (num) {
        num /= 10;
        c++;
    }
    return c;
}



/*
 * Gerador de conteúdo vetor de acordo com o tipo passado no parâmetro tipoVet.
 * Preenche o vetor vet e cVet com os mesmos valores.
 * int *vet - Vetor principal
 * int *cvet - Vetor para cópia
 * int tipoVet - Tipo de preechimento (ALEATORIO,CRESCENTE,DECRESCENTE)
 * int n - tamanho do vetor
 */
void gerarVetor(int *vet, int tipoVet, int n) {
    int i = 0;
    
    switch (tipoVet) {
        case ALEATORIO:
            srand(time(NULL));
            for (i = 0;i < n;i++) 
                vet[i] = rand() % (n * 10);
            break;

        case CRESCENTE:
            for (i = 0;i < n;i++) 
                vet[i] = i;
            break;

        case DECRESCENTE:
            for (i = 0;i < n;i++)
                vet[i] = n - i - 1;
            break;

    }
}

/* Retorna o maior elemento de um vetor de int 
 * int *V   - Vetor de inteiros
 * int n    - Tamanho do vetor
 */
int getMax(int *V,int n) {
    int maior = V[0], i;
    for (i = 1;i < n;i++)
        if (V[i] > maior)
            maior = V[i];
    return maior;
}


/**************************************
 * Métodos de ordenação não comparáveis
 **************************************/
void countingSort(int *V, int n, int max) {
    int *aux,*copia;
    int i = 0;
    aux = (int *)mallocX((max + 1) * sizeof(int));
    copia = (int *)mallocX(n * sizeof(int));

    for (i = 0;i <= max;i++)
        aux[i] = 0;

    for (i = 0;i < n;i++) 
        aux[V[i]]++;
    
    for (i = 1;i <= max;i++)
        aux[i] += aux[i - 1];
    
    for (i = n - 1;i >= 0;i--) {
        aux[V[i]]--;
        copia[aux[V[i]]] = V[i];
    }
    
    for (i = 0;i < n;i++)
        V[i] = copia[i];
    
    if (aux) free(aux);
    if (copia) free(copia);

}

void bucketSort(int *V, int n,int max) {
    int i = 0,j = 0;
    double tmp = 0;
    nodo *P;
    nodo **buckets = (nodo **)mallocX(n * sizeof(nodo *));
    
    for (i = 0;i < n;i++) 
        buckets[i] = criarLista();
    

    for (i = n - 1;i >= 0;i--) {
        tmp = (double)V[i] / (double)(max + 1);
        tmp *= (double)n;
        inserirLista(buckets[(int)tmp], V[i]);
    }
    
    j = 0;
    for (i = 0;i < n;i++) {

        selection(buckets[i]);
        P = buckets[i]->prox;
        while (P != NULL) {
            V[j] = P->info;
            P = P->prox;
            j++;
        }
        destruirLista(buckets[i]);

    }
    
    if (buckets) free(buckets);
}

void radixSort(int *V, int n, int s) {
    int i = 0,tmp = 0,base;
    int aux[10],copia[n];
    
    base = 1; 
    while (s) {
        /* countingSort */
        for (i = 0;i < 10;i++) aux[i] = 0;

        for (i = 0;i < n;i++) 
            aux[V[i] / base % 10]++;

        for (i = 1;i < 10;i++)
            aux[i] += aux[i - 1];

        for (i = n - 1; i >= 0; i--) {
            tmp = --aux[V[i] / base % 10];
            copia[tmp] = V[i];
        }

        for (i = 0;i < n; i++)
            V[i] = copia[i];
        /* countingSort */
        base *= 10;
        s--;
    }

}


void prepareHeap(int *V,int *H, int n) {
    int i;
    H[0] = 0;
    for (i = 0;i < n;i++)
        H[i+1] = V[i];
    
}

void backHeap(int *V,int *H,int n) {
    int i;
    for (i = 0;i < n;i++)
        V[i] = H[i+1];
}

void heapIfy(int *V, int n, int i) {
    int menor,aux;
    while (((i <= (n+1)/2) &amp;&amp; (V[i] > V[2*i])) || ((i < (n+1)/2) &amp;&amp; (V[i] > V[2*i + 1]))) {
        menor = 2*i;
        if ((i < (n+1)/2) &amp;&amp; (V[2 * i] >= V[2*i + 1]))
            menor = 2*i + 1;
        aux = V[i];
        V[i] = V[menor];
        V[menor] = aux;
        i = menor;
    }
}


void heapSort(int *V, int n) {
    int i,aux;

    for (i = n/2; i > 0;i--)
        heapIfy(V,n,i);
    
    for (i = 1; i < n; i++) {
        aux = V[1];
        V[1] = V[n - i + 1];
        heapIfy(V, n - i, 1);
        V[n - i + 1] = aux;
    }

    for (i = 1; i <= n/2; i++) {
        aux = V[i];
        V[i] = V[n - i + 1];
        V[n - i + 1] = aux;
    }

}

/* Lista simplesmente encadeada com cabeça */

/* Função que inicializa a lista com cabeça
 * return nodo * - Nodo que aponta para a cabeça da nova lista
 */

nodo *criarLista() {
    nodo *lista = (nodo *)mallocX(sizeof(nodo));
    lista->prox = NULL;
    return lista;
}
    
/* Função para inserir no início da lista.
 * nodo *L  - Ponteiro para cabeça da lista
 * int info - Novo valor a ser inserido
 */
void inserirLista(nodo *L,int info) {
    nodo *novo = (nodo *)mallocX(sizeof(nodo));
    novo->prox = L->prox;
    L->prox = novo;
    novo->info = info;
}

/* Libera memória para todos os nodos da lista
 * nodo *L - Ponteiro pra cabeça da lista
 */
void destruirLista(nodo *L) {
    nodo *atu;
    while (L != NULL) {
        atu = L;
        L = atu->prox;
        if (atu) free(atu);     
    }
}

/* Ordena a lista usando método de ordenação SelectionSort
 * nodo *L  - Ponteiro para cabeça da lista
 */
void selection(nodo *L) {
    nodo *i,*j;
    nodo *menor;
    int aux;
    
    if (L->prox == NULL)
        return;
    
    for (i = L->prox; i->prox != NULL;i = i->prox) {
        menor = i;
        for (j = i->prox;j != NULL;j = j->prox) {
            if (j->info < menor->info) 
                menor = j;
        }
        aux = menor->info;
        menor->info = i->info;
        i->info = aux;
    }
}