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.