GT3 :: DADOS E INFORMAÇÃO: Algoritmos de Ordenação

Bubble Sort

Primeiramente um vídeo simples e bem divertido em que é usado "Folk Dance" para explicar como ele funciona:

Bubble sort (ou método da bolha) é o algoritmo mais simples, mas o menos eficientes. Neste algoritmo cada elemento da posição i será comparado com o elemento da posição i + 1, ou seja, um elemento da posição 2 será comparado com o elemento da posição 3. Caso o elemento da posição 2 for maior que o da posição 3, eles trocam de lugar e assim sucessivamente. Por causa dessa forma de execução, o vetor terá que ser percorrido quantas vezes que for necessária, tornando o algoritmo ineficiente para listas muito grandes.

Esquema de funcionamento do Buble Sort:

É verificado se o 3 é maior que 5, por essa condição ser falsa, não há troca.
É verificado se o 5 é maior que 1, por essa condição ser verdadeira, há uma troca.
É verificado se o 5 é maior que 2, por essa condição ser verdadeira, há uma troca.
É verificado se o 5 é maior que 4, por essa condição ser verdadeira, há uma troca.
O método retorna ao início do vetor realizando os mesmos processos de comparações, isso é feito até que o vetor esteja ordenado.

Complexidade

Com relação a complexidade do algoritmo, no melhor caso, ele executa

n

operações relevantes, onde n representa o número de elementos do vetor. No pior caso, são feitas

n^2

operações. A complexidade desse algoritmo é de Ordem quadrática. Por isso, ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados.

Bubble sort
classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	$O(n^2)$
complexidade caso médio	$O(n^2)$
complexidade melhor caso	$O(n)$
complexidade de espaços pior caso	$O(1)$ auxiliar