ATPS CLASSIFICAÇÃO E PESQUISA

[pic 1]

FAC

SISTEMAS DE INFORMAÇÃO

ALUNO - R.A.:

ALUNO - R.A.:

CLASSIFICAÇÃO E PESQUISA

PROF:

ALGORITIMOS DE ORDENAÇÃO E BUSCA DE DADOS

CAMPINAS – SP

2015

---

Sumário

1.        Pesquisa de dados        

1.1.        Geração de números        

1.2.        Estrutura de dados        

1.2.1        Implementação da estrutura que representa a leitura de 1000 residências        

1.2.2        Busca Linear        

1.2.3        Busca Binária        

2.        Métodos de Ordenação        

2.1.        Ordenação por meio da seleção e troca        

2.2.        Ordenação por distribuição        

2.3.        Ordenação por inserção        

2.4.        Ordenação por intercalação        

2.5.        Comparação dos algoritmos        

2.6.        Conclusão        

3.        Bibliografia        

---

1. Pesquisa de dados

Geração de números

Para geração de números aleatórios no C, pode-se usar a função rand.

 Sua sintaxe é bem simples. A função rand utiliza um número como "semente" para gerar os números aleatórios e esse número só mudará quando a função for chamada novamente (MIZRAHI, 2007).

Exemplo:

main()

{

int i, aleatorio;

for(i = 0; i < 10; i++)

{

    aleatorio = rand();

    printf("%d\n",aleatorio);

}

system("pause");

}

Resultado do código fonte acima:

[pic 2]

(SCHILDT, 1996) Sempre que se abre o programa, os números gerados são o mesmos. Então não há, ainda, números realmente aleatórios. Se mudarmos nossa variável para receber o valor da função rand ela é chamada apenas uma vez, e sua “semente” nunca é alterada.

main()

{

int i, aleatorio = rand();

for(i = 0; i < 10; i++)

    printf("%d\n",aleatorio);

system("pause");

}

Sendo assim, neste caso acima teremos sempre o mesmo número:

[pic 3]

Para gerar números que realmente serão imprevisíveis com a função rand, devemos usar no mesmo programa outra função chamada srand (seed randomic) usada para que o número usado como semente seja sempre diferente. O uso mais comum da função srand é junto com a função time da biblioteca , que busca a data/hora do seu computador. Como o horário da execução de cada parte do programa nunca será o mesmo, a semente torna-se quase imprevisível:

#include

main()

{

srand(time(NULL));

int i, aleatorio;

for(i = 0; i < 10; i++)

{

    aleatorio = rand();

    printf("%d\n",aleatorio);

}

system("pause");

}

A cada vez que se executa esse programa um resultado diferente é fornecido.

Para gerar números aleatórios dentro de um determinado intervalo, pode-se utilizar o operador “%” (mod) que nos retorna o resto de uma divisão. Por exemplo: para simular a jogada de um dado, deveremos limitar nossos números aleatórios entre 1 à 6. Usando o operador “%” aplica-se ao valor da variável que receberá os números aleatórios o seguinte calculo: (rand() % 6)  + 1;. Qualquer número dividido por 6 retornará o resto entre 0 e 5, somando isso a 1 teremos o intervalo de 1 à 6.

#include

main()

{

srand(time(NULL));

int i, aleatorio = (rand() % 6) + 1;

printf("%d\n",aleatorio);

system("pause");

}

Código fonte para geração de números aleatórios entre 0 e 1000:

#include

int RandomInteger (int low, int high)

{

    int k;

    srand( (unsigned)time(NULL) );

    k = (rand() % high) + low;

    return k;

}

main()

{

    printf("%d\n",RandomInteger(0,1000));

}

Estrutura de dados

1. Implementação da estrutura que representa a leitura de 1000 residências

 (TENENBAUM, et al., 1995) Para simular a leitura de 1000 residências, foi criada a função RandomInteger que gera os 1000 valores de rua, número da casa, número do medidor e medida de Consumo para a struct.