Algoritmos de Ordenação

Ordenação de Bolha

O algoritmo de classificação mais simples é o de bolha. Ele funciona por iteração de uma matriz a ser ordenada a partir do primeiro elemento até o último, comparando cada par de elementos e alterando suas posições, se necessário. Esse processo é repetido tantas vezes quanto for necessário, até que a matriz seja classificada.

Como o pior caso é que a matriz está em ordem inversa e que o primeiro elemento na matriz ordenada é o último elemento na matriz inicial, a maior parte das permutas necessárias será igual ao comprimento da matriz. Aqui está um exemplo simples:

function ordenacaoBolha(vetor) {
  let n = arr.length;
  for (let i = 0; i < n - 1; i++)
    for (let j = 0; j < n - i - 1; j++)
      if (vetor[j] > vetor[j + 1]) {
        // troca temp and vetor[i]
        let temp = vetor[j];
        vetor[j] = vetor[j + 1];
        vetor[j + 1] = temp;
      }
  Console.log(vetor);
}

Dado um array [2,3,1,5,4], um tipo de bolha levaria à seguinte sequência de matrizes parcialmente ordenadas:[2,1,3,5,4], [2,1,3,4,5], [1,2,3,4,5]. Primeiro, os 1 e 3 seriam comparados e comutados, então os 4 e 5. Na próxima passagem, os 1 e 2 mudaria, e a matriz ficaria em ordem.

---

Ordenação de Seleção

O algoritmo de Ordenação de Seleção é o mais conceitualmente simples de todos os algoritmos de ordenação. Ele funciona selecionando o menor elemento (ou maior, se você deseja classificar de grande a pequeno) da matriz e colocando-o na cabeça/começo da matriz. Em seguida, o processo é repetido para o restante da matriz; o próximo elemento é selecionado e colocado no próximo espaço ao lado, e assim por diante.

Como um tipo de seleção exibe partes progressivamente menores da matriz de cada vez (como sabe ignorar a frente da matriz porque já está em ordem), um tipo de seleção é um pouco mais rápido do que o tipo de bolha e pode ser melhor do que uma ordenação tipo de bolha.

Aqui está o código para um tipo de seleção simples:

function ordenacaoSelecao(vetor) {
  let n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    //Encontra o menor item da parte não ordenada
    let min_idx = i;
    for (let j = i + 1; j < n; j++)
      if (vetor[j] < vetor[min_idx])
        min_idx = j;

    //Troca o menor com o primeiro elemento
    let temp = vetor[min_idx];
    vetor[min_idx] = vetor[i];
    vetor[i] = temp;
  }
  console.log(vetor);
}

---

Ordenação por Inserção

O Algoritmo de iteração faz exatamente o que o nome diz, ordena através da inserção de dados. Para isso, cria-se uma nova lista ou espaço na lista atual separado do resto ao qual serão colocados, 1 a 1, os itens da lista original de forma ordenada.

É muito menos eficiente em listas grandes do que algoritmos mais avançados, como quicksort, heapsort ou merge sort. No entanto, o tipo de inserção oferece várias vantagens como eficiencia para conjuntos de dados pequenos, bem como outros algoritmos de classificação quadrática, mais eficiente na prática do que a maioria dos outros algoritmos quadráticos simples (ou seja, O (n2)), como o tipo de seleção ou o tipo de bolha.

function ordenacaoInsercao(vetor)
{
    let n = vetor.length;
    for (let i=1; i<n; ++i)
    {
        let key = vetor[i];
        let j = i-1;

        //Move os elementos do vetor que são maiores que a chave para uma posição a frente 
        while (j>=0 && vetor[j] > key)
        {
            vetor[j+1] = vetor[j];
            j = j-1;
        }
        vetor[j+1] = key;
    }

    console.log(vetor);
}