Estrutura de dados unidade 2 parte 2
Método de ordenação - objetivos:
◦ Corresponde ao processo de rearranjar um conjunto de objetos j em uma ordem ascendente ou descendente.
◦ Facilitar a recuperação posterior de itens do conjunto ordenado. ◦ São largamente utilizados em Sistemas Gerenciadores de Banco de Dados (SGBDs).
◦ Em
E alguns l casos é necessário á i ffazer a avaliação li ã d da ordenação no melhor, médio e pior caso.
`
Método de ordenação Bolha (Bouble sort)
◦ Método mais conhecido;
◦ Ordenação por trocas (compara o elemento da “bolha” bolha com o próximo elemento);
◦ Troca de valores entre posições consecutivas;
◦ Ordenação sequencial (percorre o vetor e compara elemento a elemento, mesmo que tal elemento ou todos d já estejam j ordenados) d d )
◦ Recomendado, portanto, para vetores com poucos elementos. elementos
`
Método de ordenação Bolha (Bouble sort)
◦ A ordenação bolha é feita através de dois laços. O laço mais externo, da variável cont1, determina qual elemento do vetor será usado como base de comparação (a “bolha”). O laço mais interno, da variável cont2,, compara p cada item com o elemento base do primeiro laço e, quando encontrar um item menor que o de base, faz a troca.
◦ O processo de troca usa uma variável temporária (temp) para guardar o valor do menor valor, inicialmente; depois põe na posição que antes era ocupada pelo depois, item do laço mais interno, o valor do item de base; finalmente, atribui o valor armazenado na variável temporária (o menor valor) ao elemento base. A troca esta concluída.
`
Método de ordenação Bolha (Bouble sort)
◦ Ex: Ordenar os elementos de um vetor vet, com 3 posições, respectivamente 12,8 e 3.
◦ Passo
P
1:
1 fixar fi a bolha b lh no primeiro i i elemento l t d do vetor t vet:
0
1
2
12
8
vet[0]
vet[1]
3
vet[2]
`
Método de ordenação Bolha (Bouble sort)
◦ Passo 2: comparar o elemento l d da b bolha lh com o próximo ó elemento se for maior, faz a troca, seguindo os passos:
x A) O menor elemento é armazenado na variável