Estruturas de Dados Avançadas

˜
UNIVERSIDADE ESTADUAL DO MARANHAO-UEMA
ˆ
´
CENTRO DE CIENCIAS TECNOLOGICAS-CCT
ENGENHARIA DE COMPUTACAO
¸˜

ESTRUTURAS DE DADOS AVANCADAS
¸

Aluno:

Brasil
2014

Trabalho de Avalia¸˜o ca 1. Modifique o algoritmo Quicksort de forma a ele utilizar um outro m´todo de ordena¸ao e c˜ simples para quando as cole¸oes ficarem menores (preferencialmente inser¸ao). c˜ c˜
O algoritmo foi modificado de modo que quando o procedimento QuickSort for chamado em um subarranjo com menos de k elementos, executa a ordena¸ao por inser¸˜o sobre o arranjo c˜ ca inteiro, a fim de concluir o processo de ordena¸ao. Segundo Thomas H. Cormen no seu livro c˜ ”Introduction to Algorithms - Second Edition”, este algoritmo misto ´ executado no tempo e esperado O(nk + n log(n/k)).
Abaixo segue o algoritmo Quick Sort modificado implementado em Linguagem C
Listing 1: QuickSortMod.c
# include
# include
# include
# include

< stdio .h >
< time .h >
< stdlib .h >
< math .h >

# define MaxTam 1000000
# define MaxRand 1000
# define Max 10000
// Quick Sort Modificado
// utiliza um outro m´ todo de ordena¸ ~ o simples quando e ca
// as cole¸ ~ es ficam menores co void imprimir_lista () ; typedef struct { int chave ;
} TItem ;
TItem lista [ MaxTam ]; void iniciar_lista () {
// Inicializar o gerador de n´ meros aleat´ rios u o
// Com time ( NULL ) srand ( time ( NULL ) ) ; int i ; for ( i = 0; i < MaxTam ; i ++) { lista [ i ]. chave = rand () % MaxRand ;
}
} void preencher_lista ()
{
int i ; for ( i = 0; i < MaxTam ; i ++)
{
printf ( " \ n % d % c elemento : " ,i +1 ,167) ; scanf ( " % d " ,& lista [ i ]. chave ) ;
}

1

} void InsertionSort ( int tam ) { int i , j ;
TItem value ; for ( i = 1; i < tam ; ++ i ) { value . chave = lista [ i ]. chave ; for ( j = i - 1; j >= 0 && lista [ j ]. chave > value . chave ; ...
--j ) { lista [ j + 1] = lista [ j ]; lista [ j ] = value ;
}
}
}
void troca ( int i , int j )
{
TItem