Algoritmos de ordenação de arrays com JavaScript

Algoritmos de ordenação de arrays com JavaScript

Neste artigo você vai ser exemplos de implementação de algoritmos de ordenação utilizando JavaScript. Vamos abordar algoritmos de ordenação bem conhecidos, como Merge Sort, Quick Sort e Bubble Sort.

 

MERGE SORT

 

O Merge Sort é um algoritmo de ordenação que divide repetidamente o array em duas metades até que cada subarray tenha apenas um elemento. Posteriormente ele combina estas partes de maneira ordenada.

 

Vamos ver primeiro uma implementação deste algoritmo, e a seguir a sua explicação:

 

function mergeSort(arr) {

  // Arrays com menos de 2 elementos já estão ordenados..

  if (arr.length <= 1) {

    return arr;

  }

  // Divide o array em duas metades

  const meio = Math.floor(arr.length / 2);

  const esquerda = arr.slice(0, meio);

  const direita = arr.slice(meio);

  // Recursivamente ordena cada metade

  return merge(mergeSort(esquerda), mergeSort(direita));

}

function merge(esquerda, direita) {

  let resultados = [];

  let indiceEsquerda = 0;

  let indiceDireita = 0;

  // Compara cada elemento dos arrays esquerda e direita e mescla eles em ordem

  while (indiceEsquerda < esquerda.length && indiceDireita < direita.length) {

    if (esquerda[indiceEsquerda] < direita[indiceDireita]) {

      resultados.push(esquerda[indiceEsquerda]);

      indiceEsquerda++;

    } else {

      resultados.push(direita[indiceDireita]);

      indiceDireita++;

    }

  }

  // Concatena qualquer elemento remanescente com o array esquerda ou direita.

  return resultados.concat(esquerda.slice(indiceEsquerda)).concat(direita.slice(indiceDireita));

}

// Exemplo de uso:

const array = [38, 27, 43, 3, 9, 82, 10];

const arrayOrdenado = mergeSort(array);

console.log(arrayOrdenado); // [3, 9, 10, 27, 38, 43, 82]

 

Você pode ver que nesta implementação nós chamamos a função mergeSort. Internamente, ela utilizou a função merge. Vamos entender o nosso código.

A função mergeSort fez as seguintes operações:

1 - Verifica se o array tem um ou nenhum elemento (caso base). Se sim, ele já está ordenado e é retornado.

2 - Caso contrário, divide o array em duas metades: esquerda e direita.

3 - Recursivamente aplica o mergeSort em cada metade.

4 - Usa a função auxiliar merge para combinar as duas metades ordenadas em um único array ordenado.

Já a função auxiliar merge inicializa um array chamado resultados e variáveis auxiliares chamadas indiceEsquerda e indiceDireita para percorrer os arrays esquerda e direita. Depois ela compara os elementos dos arrays esquerda e direita, adicionando o menor elemento ao array resultados e incrementando o índice correspondente (indiceEsquerda ou indiceDireita).

Quando todos os elementos de esquerda ou direita forem adicionados, concatena os elementos restantes do outro array ao resultados.

 

QUICK SORT

 

O Quick Sort é um algoritmo de ordenação que utiliza um pivô  rearranjando os elementos do array de forma que os elementos menores que o pivô fiquem à esquerda e os maiores à direita. Depois, o algoritmo é recursivamente aplicado às subpartes esquerda e direita. Existem várias estratégias para escolher o pivô, como escolher o primeiro, o último, ou o elemento do meio.

Aqui está um exemplo de implementação deste algoritmo:

 

function quickSort(arr) {

  // Arrays com menos de 2 elementos já estão ordenados..

  if (arr.length <= 1) {

    return arr;

  }

  // Seleção do alemento pivô. Neste caso foi selecionado o elemento do meio

  const pivot = arr[Math.floor(arr.length / 2)];

  // Arrays para guardar elementos menores, iguais ou maiores que o pivot

  let esquerda = [];

  let direita = [];

  let igual = [];

  // Dividir o array e inserir o conteudo nos arrays esqueda, igual ou direita

  for (let i = 0; i < arr.length; i++) {

    if (arr[i] < pivot) {

      esquerda.push(arr[i]);

    } else if (arr[i] > pivot) {

      direita.push(arr[i]);

    } else {

      igual.push(arr[i]);

    }

  }

  // Recursivamente ordenar os arrays esquerda e direita e concatenar os resultados

  return quickSort(esquerda).concat(igual, quickSort(direita));

}

// Exemplo de uso:

const array = [38, 27, 43, 3, 9, 82, 10];

const arrayOrdenado = quickSort(array);

console.log(arrayOrdenado); // [3, 9, 10, 27, 38, 43, 82]

 

Vamos a explicação do que a função quickSort fez:

1 - Ao iniciar, ela verifica se o array tem um ou nenhum elemento (caso base). Se sim, ele já está ordenado e é retornado.

2 - Escolhe um pivô. Neste caso, escolhemos o elemento do meio do array.

3 - Inicializa três arrays: esquerda para elementos menores que o pivô, direita para elementos maiores que o pivô, e igual para elementos iguais ao pivô.

4 - Percorre o array, comparando cada elemento com o pivô e adicionando-o ao array correspondente (esquerda, direita, ou igual).

5 - Recursivamente aplica o quickSort às subpartes esquerda  e direita, e concatena os resultados com o array igual.

 

BUBBLE SORT

O Bubble Sort é um algoritmo simples de ordenação que compara repetidamente pares adjacentes de elementos e os troca se estiverem na ordem errada. 

Uma implementação deste algoritmo pode ser vista a seguir:

 

function bubbleSort(arr) {

  let n = arr.length;

  let substituir;

  do {

    substituir = false;

    for (let i = 1; i < n; i++) {

      if (arr[i - 1] > arr[i]) {

        [arr[i - 1], arr[i]] = [arr[i], arr[i - 1]];

        substituir = true;

      }

    }

    n--;

  } while (substituir);

  return arr;

}

// Exemplo de uso:

const array = [38, 27, 43, 3, 9, 82, 10];

const arratOrdenado = bubbleSort(array);

console.log(arratOrdenado); // [3, 9, 10, 27, 38, 43, 82]

 

As operações que a função bubbleSort fez foram as seguintes:

1 - São iniciadas duas variáveis,  "n" é o comprimento do array e o "substituir" é uma variável booleana que indica se houve uma troca durante uma iteração.

2 - Utilizando um laço do-while, o valor de substituir é definido como false para iniciar a iteração. O laço percorre o array do índice 1 até n-1.

3 - Se o elemento anterior arr[i - 1] é maior que o atual arr[i], eles são trocados usando a desestruturação de array.

Após a troca, substituir é definido como true para indicar que houve uma troca nesta iteração.

4 - O tamanho do array a ser verificado é reduzido em 1, pois após cada iteração, o maior elemento é colocado na sua posição correta.

5 - O laço do-while continua enquanto substituir for true, ou seja, enquanto houver trocas, o laço continua executando.

6 - Após o array estar ordenado, o array ordenado é retornado.

 

CONCLUSÃO

 

Para a maioria dos casos práticos, o Quick Sort é geralmente a escolha mais eficiente em termos de desempenho, desde que seja usada uma boa estratégia de escolha de pivô. O Merge Sort é uma excelente alternativa quando a estabilidade é necessária e o uso de memória adicional não é um problema. O Bubble Sort é mais adequado para pequenos conjuntos de dados ou para fins educacionais devido à sua simplicidade, mas não é recomendado para grandes conjuntos de dados devido à sua ineficiência.

 

ENCERRAMENTO

 

Neste artigo você viu os algoritmos de ordenação Merge Sort, Quick Sort e Bubble Sort.

Tem interesse de saber mais sobre operações com arrays no JavaScript? Se a sua resposta for sim não deixe de conferir estes artigos:

Métodos para trabalhar com arrays no JavaScript

Ordenar arrays com Javascript

Remover elementos de um array com JavaScript

Separando um array de strings em conjuntos de arrays ordenados alfabeticamente com JavaScript

 

 

Está começando e deseja saber o que precisa estudar de HTML e JavaScript? Não deixe de conferir os roteiros de estudo de HTML e JavaScript!. São dezenas de conteúdos para você melhorar suas habilidades.

Roteiro de estudos - HTML e CSS

Roteiro de estudos - Javascript

 

Outros conteudos que podem ser de seu interesse

Resolvendo problemas comuns de matemática com JavaScript
03/07/2022JAVASCRIPT

Resolvendo problemas comuns de matemática com JavaScript

Descubra como o JavaScript pode te ajudar a resolver problemas comuns de matemática

Saiba mais...
Ferramentas de Inteligência Artificial para edição de imagens e vídeos
10/12/2023JAVASCRIPT

Ferramentas de Inteligência Artificial para edição de imagens e vídeos

Uma lista de sites com ferramentas de IA para editar imagens e vídeos

Saiba mais...

Conteúdo sobre banco de dados sem complicação!