Como Funciona o Bubble Sort

Este documento explica o algoritmo de ordenação #Bubble Sort, detalhando seu funcionamento passo a passo com um exemplo prático em JavaScript. O objetivo é fornecer uma compreensão clara de como o #algoritmo compara e troca elementos adjacentes para ordenar uma lista de números.

Bubble Sort: Uma Explicação Detalhada

O Bubble Sort é um algoritmo de ordenação simples que repetidamente percorre a lista, compara elementos adjacentes e os troca se estiverem na ordem errada. A passagem pela lista é repetida até que nenhum elemento precise ser trocado, o que indica que a lista está ordenada.

Exemplo Prático em JavaScript

Vamos analisar o código JavaScript fornecido para entender melhor o Bubble Sort:

const numeros = [35, 8, 1, 4];

function bubbleSort(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length - 1 - i; j++) {
      // aqui dentro vamos comparar e trocar
      if (array[j] > array[j + 1]) {
        let temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
      console.log(i, array);
    }
  }
  return array;
}

console.log(bubbleSort(numeros));

Passo a Passo do Algoritmo

1. Array Inicial:

*   `numeros = [35, 8, 1, 4]`

2. Loop Externo (i):

*   O loop externo controla o número de passagens pela lista. A cada passagem, o maior elemento "flutua" para o final da lista (como uma bolha, daí o nome "Bubble Sort").

*   `for (let i = 0; i < array.length; i++)`

3. Loop Interno (j):

*   O loop interno compara e troca elementos adjacentes.

*   `for (let j = 0; j < array.length - 1 - i; j++)`

*   Note que `array.length - 1 - i` otimiza o loop, pois a cada passagem do loop externo, o último `i` elementos já estão ordenados.

4. Comparação e Troca:

*   `if (array[j] > array[j + 1])`

*   Se o elemento atual (`array[j]`) for maior que o próximo elemento (`array[j + 1]`), eles são trocados.

*   A troca é feita usando uma variável temporária (`temp`).

```javascript

let temp = array[j];

array[j] = array[j + 1];

array[j + 1] = temp;

```

5. Exemplo Detalhado:

Vamos acompanhar a execução do algoritmo com o array `[35, 8, 1, 4]`.

*   **Primeira Passagem (i = 0):**

    *   `j = 0`: `35 > 8`? Sim. Troca: `[8, 35, 1, 4]`

    *   `j = 1`: `35 > 1`? Sim. Troca: `[8, 1, 35, 4]`

    *   `j = 2`: `35 > 4`? Sim. Troca: `[8, 1, 4, 35]`

    *   `console.log(0, [8, 1, 4, 35])`

*   **Segunda Passagem (i = 1):**

    *   `j = 0`: `8 > 1`? Sim. Troca: `[1, 8, 4, 35]`

    *   `j = 1`: `8 > 4`? Sim. Troca: `[1, 4, 8, 35]`

    *   `console.log(1, [1, 4, 8, 35])`

*   **Terceira Passagem (i = 2):**

    *   `j = 0`: `1 > 4`? Não.

    *   `j = 1`: `4 > 8`? Não.

    *   `console.log(2, [1, 4, 8, 35])`

*   **Quarta Passagem (i = 3):**

    *   `j = 0`: `1 > 4`? Não.

    *   `console.log(3, [1, 4, 8, 35])`

6. Retorno:

*   Após as passagens, o array estará ordenado: `[1, 4, 8, 35]`

*   `return array;`

7. Resultado:

*   `console.log(bubbleSort(numeros));` imprime `[1, 4, 8, 35]`

Complexidade do Bubble Sort

• Pior Caso e Caso Médio: O(n^2) - Onde 'n' é o número de elementos no array. Isso ocorre quando o array está em ordem inversa, exigindo o máximo de comparações e trocas.

• Melhor Caso: O(n) - Ocorre quando o array já está ordenado. Nesse caso, o algoritmo faz apenas uma passagem para verificar se há trocas necessárias.

• Espaço: O(1) - O Bubble Sort é um algoritmo de ordenação "in-place", o que significa que ele não requer espaço adicional significativo além do espaço ocupado pelo array original.

Vantagens e Desvantagens

• Vantagens:

  • Simples de entender e implementar.

  • Fácil de detectar se o array já está ordenado (melhor caso O(n)).

• Desvantagens:

  • Ineficiente para grandes conjuntos de dados devido à sua complexidade O(n^2) no pior caso e caso médio.

  • Não é adequado para arrays grandes ou aplicações onde a velocidade de ordenação é crítica.

Quando Usar o #Bubble Sort?

O Bubble Sort é geralmente usado para fins educacionais ou para ordenar pequenos conjuntos de dados onde a simplicidade do código é mais importante do que a eficiência. Para conjuntos de dados maiores, algoritmos de ordenação mais eficientes, como Merge Sort, Quick Sort ou Heap Sort, são preferíveis.

Em resumo, o Bubble Sort é um algoritmo de ordenação básico que ilustra claramente o conceito de comparação e troca de elementos para ordenar uma lista. Embora não seja o mais eficiente, sua simplicidade o torna útil para aprender os fundamentos da ordenação de dados.