Resumo de Bubble sort (ordenação por bolha)

## Ordenação por Bolha (Bubble Sort) A Ordenação por Bolha, ou **Bubble Sort**, é um dos algoritmos de ordenação mais básicos e fáceis de entender. Seu nome vem da ideia de que os elementos maiores "borbulham" para o final da lista, enquanto os menores "afundam" para o início, similar às bolhas de ar subindo na água. Embora seja simples, não é eficiente para grandes volumes de dados e é mais usado para ensinar os fundamentos dos algoritmos de ordenação. ### Princípio de Funcionamento O Bubble Sort funciona **comparando e trocando elementos adjacentes**. Ele percorre a lista várias vezes. Em cada passagem, compara pares de elementos vizinhos e os troca se estiverem na ordem errada. Isso garante que, ao final de cada passagem completa, o maior elemento não ordenado esteja na sua posição final correta. A lista é considerada ordenada quando uma passagem inteira acontece sem nenhuma troca. > **Elemento Adjacente:** Refere-se a elementos que estão um ao lado do outro na sequência, como o elemento na posição $i$ e o elemento na posição $i+1$. Vamos detalhar o processo: 1. **Comparação**: O algoritmo começa comparando o primeiro par de elementos (índice $0$ e $1$) da lista. 2. **Troca**: Se o elemento no índice $0$ for maior que o elemento no índice $1$, eles são trocados de posição. Caso contrário, permanecem como estão. 3. **Avanço**: O algoritmo então se move para o próximo par de elementos (índice $1$ e $2$) e repete a comparação e, se necessário, a troca. 4. **Propagação**: Este processo continua até o final da lista. Ao final da primeira passagem, o maior elemento da lista estará garantidamente na última posição. 5. **Repetição**: O algoritmo repete as passagens, mas a cada nova passagem, o último elemento já estará ordenado e não precisa mais ser considerado. Assim, o número de comparações em cada passagem diminui progressivamente. 6. **Condição de Parada**: O algoritmo para quando uma passagem completa é feita sem que nenhuma troca ocorra, indicando que a lista está totalmente ordenada. ### Exemplo Detalhado de Ordenação Vamos considerar uma lista de números inteiros desordenados: $[5, 1, 4, 2, 8]$. Iremos ordenar esta lista em ordem crescente usando a Ordenação por Bolha. **Lista inicial:** $[5, 1, 4, 2, 8]$ **Primeira Passagem:** * Comparar $5$ e $1$: $5 > 1$, então troca. Lista: $[1, 5, 4, 2, 8]$ * Comparar $5$ e $4$: $5 > 4$, então troca. Lista: $[1, 4, 5, 2, 8]$ * Comparar $5$ e $2$: $5 > 2$, então troca. Lista: $[1, 4, 2, 5, 8]$ * Comparar $5$ e $8$: $5 < 8$, não troca. Lista: $[1, 4, 2, 5, 8]$ Ao final da primeira passagem, o maior elemento ($8$) está na sua posição final. O último elemento ($8$) está agora ordenado. **Segunda Passagem:** (Consideramos apenas os primeiros $4$ elementos: $[1, 4, 2, 5]$) * Comparar $1$ e $4$: $1 < 4$, não troca. Lista: $[1, 4, 2, 5, 8]$ * Comparar $4$ e $2$: $4 > 2$, então troca. Lista: $[1, 2, 4, 5, 8]$ * Comparar $4$ e $5$: $4 < 5$, não troca. Lista: $[1, 2, 4, 5, 8]$ Ao final da segunda passagem, o segundo maior elemento ($5$) está na sua posição final. Os dois últimos elementos ($5$, $8$) estão agora ordenados. **Terceira Passagem:** (Consideramos apenas os primeiros $3$ elementos: $[1, 2, 4]$) * Comparar $1$ e $2$: $1 < 2$, não troca. Lista: $[1, 2, 4, 5, 8]$ * Comparar $2$ e $4$: $2 < 4$, não troca. Lista: $[1, 2, 4, 5, 8]$ Ao final da terceira passagem, o terceiro maior elemento ($4$) está na sua posição final. Os três últimos elementos ($4$, $5$, $8$) estão agora ordenados. **Quarta Passagem:** (Consideramos apenas os primeiros $2$ elementos: $[1, 2]$) * Comparar $1$ e $2$: $1 < 2$, não troca. Lista: $[1, 2, 4, 5, 8]$ Ao final da quarta passagem, o quarto maior elemento ($2$) está na sua posição final. Os quatro últimos elementos ($2$, $4$, $5$, $8$) estão agora ordenados. **Quinta Passagem:** (Consideramos apenas o primeiro elemento: $[1]$) * Nenhuma comparação é feita, pois há apenas um elemento. Como na quarta passagem não hou