Analise de algoritmos

Analise de Algoritmos II

Professor: Leandro S. Marques Eduardo Moreira Pinto nº03 Rgm:074984

Salto
2012

Implementação do Código em C++

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

#define Max 500000
#define num_bucket 10
#define tam_bucket 10

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

void insertionsort(int v[Max], int n)
{
int i, j, aux; for (i = 1; i < n; i++)
{
aux = v[i]; j = i -1; while ( (j>=0) && (aux < v[j]))
{
v[j+1] = v[j]; j--; } v[j+1] = aux;
}
}

typedef struct{ int topo; int balde[tam_bucket];
}bucket;

void bucket_sort(int v[],int tam){ bucket b[num_bucket]; int i,j,k; for(i=0;i<num_bucket;i++) b[i].topo=0; for(i=0;i<tam;i++){ j=(num_bucket)-1; while(1){ if(j<0) break; if(v[i]>=j*10){ b[j].balde[b[j].topo]=v[i]; (b[j].topo)++; break; } j--; } }
/* 3 */ for(i=0;i<num_bucket;i++) //ordena os baldes if(b[i].topo) insertionsort(b[i].balde,b[i].topo); i=0; /* 4 */ for(j=0;j<num_bucket;j++){ //põe os elementos dos baldes de volta no vetor
for(k=0;k<b[j].topo;k++){