Unip - Banco de Dados - Aps

Sumário

Introdução        

Referencial Teórico        

Desenvolvimento        

Resultado e considerações finais        

Referências Bibliográficas        

Introdução

Há algum tempo, um tanto quanto longínquo do atual, o ser humano se vê na necessidade de guardar informações, sejam elas de quaisquer tipos, tamanho ou interesse.

Visto que precisamos guardar informações, não podemos fazer isso de qualquer modo, precisamos de um meio de organizá-las. Daí então que surgiu a ordenação de dados, que em um modo simples e básico de se falar, é a organização de informações tanto por meio alfabético, ordinal ou até mesmo lexicográfica.

Existem muitos tipos de métodos ordenação de dados, mas nesse trabalho iremos mostrar e exemplificar alguns dos métodos utilizados nos dias de hoje.

O método Selection sort (Seleção direta), é um método no qual ele pesquisa os dados que se encontram no vetor, analisa todos um a um na procura do menor elemento, após fazer essa análise e encontrar o menor valor do vetor o mesmo coloca esse elemento na primeira posição consequentemente ele volta a analisar o vetor para pegar o segundo menor valor para colocá-lo na segunda posição, assim sucessivamente para poder ordenar todos elementos até que todos fiquem em uma ordem crescente da esquerda para a direita.

O método Bubble sort (Bolha), este método faz uma comparação dos elementos com seu anterior, ou seja, ele compara o segundo valor de um vetor seguindo tanto da esquerda para direita como vice versa, e se caso o valor seja menor que o outro, ele efetua as trocas dos elementos até que os mesmos estejam ordenados.

O método Insert sort (Inserção), este tipo de ordenação, age de um modo bem simples, o que ele faz e pegar o primeiro elemento e comparar com o resto dos elementos que se encontram no vetor e posiciona-lo na posição correta conforme sua ordenação, no caso ele compara o primeiro elemento do vetor com os seguintes, se o mesmo for menor que todos ele o posiciona na primeira posição, caso contrário ele compara os outros elementos até achar o menor e ir posicionando cada qual no seu lugar.

O método Quick sort , um método bastante utilizado, é conhecido basicamente como o método “dividir para se conquistar”, o quick sort funciona da seguinte maneira, ele escolhe aleatoriamente um pivô dos dados inseridos no vetor, após escolher esse pivô ele divide o vetor em duas partes, colocando os dados maiores que seu pivô a sua direita, e os menores a sua esquerda, assim achando a posição correta do pivô, após organizar os dois lados, o mesmo passa para uma das tabelas e escolhe outro pivô e repete o procedimento, até que os dados no vetor estejam corretamente ordenados.

Estes quatro métodos apresentados acima, são tipos de ordenação bem utilizados, claro que cada qual tem seu ponto de vantagem e desvantagem, conforme elaboramos e construímos este trabalho, fizemos uma escolha de três métodos dentre esses quatro, iremos mostrar o por que escolhemos os métodos insertion sort, selection sort e bubble sort, iremos também mostrar o porquê de não termos escolhido o método quick sort.

Toda escolha foi feita embasada em testes e elaboração do código desenvolvido por nós, e pelos resultados que o mesmo demonstrou.

Para cada processo iremos mostrar um resumo e um exemplo do que cada parte do código faz em seu processo, e uma descrição também da linha de código.

Referencial Teórico

Bubble Sort: O método Bubble sort é o mais simples dos algoritmos de comparação. Esse método compara os elementos adjacentes (dois a dois), por exemplo: compara-se a primeira posição do vetor com a segunda, na segunda repetição, compara-se a segunda posição do vetor com a terceira, e assim sucessivamente, assim podemos ordenar o vetor de forma crescente ou decrescente.

Abaixo um exemplo simples de ordenação em ordem crescente de valores.

5 - 3 - 1 - 4 - 2

Primeiro compara-se as duas primeiras posições, nesse caso o número 5 e 3; caso o primeiro número seja maior que o segundo, deve-se fazer uma troca. Como 5 é maior que 3, deve-se fazer a troca:

3 - 5 - 1 - 4 - 2

5 é maior que 1, então:

3 - 1 - 5 - 4 - 2

5 é maior que 4, logo:

3 - 1 - 4 - 5 - 2

e por último, 5 é maior que 2:

3 - 1 - 4 - 2 - 5

Repare que o último item esta em seu lugar adequado. Agora é necessário ordenar o resto da sequência.

3 é maior que 1:

1 - 3 - 4 - 2 - 5

4 é maior que 2:

1 - 3 - 2 - 4 - 5

4 já está em sua posição certa, então deverá aplicar o algoritmo novamente porém somente até a terceira posição, assim chegado ao resultado desejado:
1 - 2 - 3 - 4 - 5 

Uma desvantagem é a lentidão, pois o método percorre todo o vetor diversas vezes, por isso, não é recomendado o uso dele para aplicações que requerem velocidade ou trabalhem com uma grande quantidade de dados.

Método Selection: este método funciona da seguinte maneira: seleciona o menor item do vetor faz uma troca com a primeira posição do vetor. Isto acontece respectivamente para n-1 elementos restantes, em seguida com n-2 até que reste apenas um elemento. As diferenças desses métodos entre os outros é que ele realiza apenas uma troca por interação. Na figura abaixo podemos ver como funciona:

[pic 1]

Um método simples embora estável, com tempo de execução linear, é uma boa escolha para arquivos com registros grandes, tem fácil implementação, com um pequeno número de movimentações, ótimo para arquivos pequenos.

Insert sort: Este método se mostra muito eficiente e simples de se trabalhar quando tratamos de um vetor com poucos elementos, basicamente o que este algoritmo faz é ir pegando os elementos do vetor e ir posicionando cada um em sua posição devida de uma forma crescente.

Um algoritmo que age de forma rápida e precisa, claro que quando falamos de um vetor maior ou quanto mais formos inserindo dados em um vetor para este tipo de algoritmo ele age de maneira mais lenta, pois o mesmo compara todos os elementos do vetor para pode-los colocar na posição ordenada.

...