Metodos de Ordenacao

SUMÁRIO
Conteúdo

1. BubbleSort
1 Descrição
Essa técnica consiste em analisar sequencialmente cada um dos elementos do vetor, comparando os elementos vizinhos entre si. Por exemplo: compara-se a primeira posição do vetor com a segunda, na segunda iteração, compara-se a segunda posição do vetor com a terceira, e assim sucessivamente. Caso dois elementos consecutivos estejam fora de ordem, os mesmos trocam de posição. Desta forma, os maiores elementos tendem a deslocar-se para a direita do vetor e os menores para a esquerda. O vetor fica ordenado quando após várias passagens, com pelo menos uma troca, não há qualquer troca na passagem atual.
De acordo com o algoritmo, podemos ordenar o vetor de forma crescente ou decrescente. Este algoritmo recebeu este nome em analogia a bolhas (bubble) que, sendo mais leves que a água, flutuam até a superficie, assim como os números menores que “flutuam” até o fim da lista sendo ordenada.

2 Algoritmo e Análise de Complexidade

void BubbleSort (int V[ ], int n)
{
int aux, i, j; a operações for ( j = n-1; j >= 1; j--) { for (i=0; iV[i+1]) { n-1 aux = V[i]; b operações n-1 V[i] = V[i+1]; V[i+1] = aux; } } }
}

Complexidade teórica no pior caso (sendo a e b constantes):
T(n) ≤ a +
T(n) ≤ a +
T(n) ≤ a +
T(n) ≤ a +
T(n) ≤
T(n) = Θ

3 Propriedades do Algoritmo
No melhor caso, onde a entrada já está ordenada, a complexidade do método Bubble Sort será Θ(n), pois não haverá nenhuma troca, logo, apenas um laço mais interno com n iterações, já que o mais externo terá somente uma iteração.
Para o caso médio, aonde a entrada é aleatoriamente distribuída, o Bubble sort não é eficiente. Sua complexidade é um pouco abaixo de Θ, que é