Metodos de Ordenação

main.c

/*
    Universidade Estadual Paulista "Júlio de Mesquita Filho"
    Campus de São José do Rio Preto - IBILCE

    DCCE :: Departamento de Ciências de Computação e Estatística
    Docente: Geraldo Francisco Donegá Zafalon
    Discente: Victor Hugo Bernardes de Souza
    R.A.: 09107-3
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#define TAMANHO 100000

void piorcaso();

int* gPiorCaso();   //Gera vetor para Pior caso = vetor não ordenado
int* gMedioCaso();  //Gera vetor para Medio caso = vetor semi-ordenado
int* gMelhorCaso(); //Gera vetor para Melhor caso = Vetor ordenado

double tempo();

void bolha(int *v,int n);
void selecao(int *v, int n);
void insercao(int *v, int n);
void shellsort(int *v, int n);
void quicksort(int *v, int inicio, int fim);
int verifica_ordem(int *v, int n);

int main()
{
    int n, elem, met,opcao,i, *vetor, *vetor_aux;

    piorcaso();
    return 0;
}

void piorcaso()
{
    int *vetor;

    double inicial,info[6]; //Bolha, Seleção, Inserção, Quick, Heap, Shell

    vetor = gPiorCaso();

    inicial = tempo();
    bolha(vetor,TAMANHO);
    info[0]=tempo()-inicial;

    printf("hahah %f",info[0]);
}

int* gPiorCaso()  //Gera vetor para Pior caso = vetor não ordenado
{
    int i, *vetor;
    vetor = (int*) malloc(sizeof(int) * TAMANHO);

    for(i=TAMANHO; i>0; i--)
        vetor[TAMANHO-i] = i;

    return vetor;
}

int* gMedioCaso() //Gera vetor para Medio caso = vetor semi-ordenado
{
    int i, j, meioTamanho=TAMANHO/2, *vetor;
    vetor = (int*) malloc(sizeof(int) * TAMANHO);

    for(i=0; i<meioTamanho; i++)
        vetor[i] = i;

    for(i=TAMANHO-1,j=meioTamanho; i>=meioTamanho; i--,j++){
        vetor[i] = j;
    }
    return vetor;
}

int* gMelhorCaso() //Gera vetor para Melhor caso = Vetor ordenado
{
    int i, *vetor;
    vetor = (int*) malloc(sizeof(int) * TAMANHO);

    for(i=0; i<TAMANHO; i++)
        vetor[i] = i;

    return vetor;
}

double tempo()
{
    //return (double) clock()/CLOCKS_PER_SEC;
    struct timeval instante;

    gettimeofday(&instante, NULL);
    return instante.tv_sec+(instante.tv_usec/1000000.0);
}

void bolha(int *v,int n)
{
    int i,j,aux;
    for(i=0; i<n-1; i++)
    {
        for(j=i+1; j<n; j++)
        {
            if(v[i] > v[j])
            {
                aux=v[i];
                v[i]=v[j];
                v[j]=aux;
            }
        }
    }
}

void selecao(int *v, int n)
{
    int i,j,menor,aux;
    for(i=0; i<n-1; i++)
    {
        menor=i;
        for(j=i+1; j<n; j++)
            if(v[j]<v[menor])
                menor=j;
        aux=v[i];
        v[i]=v[menor];
        v[menor]=aux;
    }
}

void insercao(int *v, int n)
{
    int i,j,aux;


    for(j=1; j<n; j++)
    {
        aux=v[j];
        for(i=j-1; i>=0 && v[i]>aux; i--)
            v[i+1]=v[i];
        v[i+1]=aux;
    }

}

void shellsort(int *v, int n)
{
    int x, i, j, k, passo[5], inc;
    passo[0] = 9;
    passo[1] = 7;
    passo[2] = 5;
    passo[3] = 3;
    passo[4] = 1;

    for (k=0; k<5; k++)
    {
        inc = passo[k];
        for (i=inc; i<n; i++)
        {
            x = v[i];
            for (j=i-inc; j>=0 && v[j]>x; j=j-inc)
                v[j+inc] = v[j];
            v[j+inc] = x;
        }
    }
}

void quicksort(int *v, int inicio, int fim)
{

    int i, j, x, aux;
    x = v[(inicio+fim)/2];
    i=inicio;
    j=fim;

    while (i<=j)
    {
        while ( v[i] < x && i < fim ) i++;
        while ( v[j] > x && j > inicio) j--;

        if ( i <= j )
        {
            aux = v[i];
            v[i] = v[j];
            v[j] = aux;
            i++;
            j--;
        }

    }

    if ( j > inicio )
        quicksort(v, inicio, j);
    if ( i < fim )
        quicksort(v, i, fim);
}

int verifica_ordem(int *v, int n)
{
    int i=0, aux = 1;

    while(aux==1 && i < n-1)
    {
        if (v[i] > v[i+1])
            aux = 0;
        i++;
    }
    return aux;
}