Introdução ao Merge Sort in JavaScript
Os algoritmos de classificação são muito importantes em Ciência da Computação. A saída da classificação é organizar os elementos de uma lista em uma determinada ordem (crescente ou decrescente). Mesclar classificação no JavaScript é um dos algoritmos de classificação mais eficientes disponíveis, pois se baseia no conceito de divisão e conquista. Como o nome sugere, primeiro divida o problema maior em problemas pequenos do que resolva os problemas menores para resolver o problema maior. Conceitualmente, a classificação de mesclagem é uma combinação de dois algoritmos básicos chamados MERGE e MERGE_SORT.
que funciona da seguinte maneira:
- Divida a lista não classificada em n número de sub-listas de item único (n é o número total de elementos na lista não classificada).
- Mesclar sublistas repetidamente em sublistas classificadas até que haja apenas uma lista classificada.
Implementação da classificação de mesclagem em JavaScript
O algoritmo MERGE segue o procedimento de combinar duas listas classificadas em uma lista classificada.
Exemplo: Suponha que haja duas listas, ou seja, Lista 1 (1, 5, 3) e Lista 2 (7, 2, 9).
1. Primeiro, classifique as duas listas.
Agora, veremos e aplicaremos a técnica E nela.
2. Em seguida, criaremos uma nova lista de tamanho x + y, em que x é o número de elementos na Lista 1 e y é o número de elementos na Lista 2.
No nosso caso x = 3 e y = 3, então x + y = 6.
3. Agora, temos dois ponteiros.
Um primeiro ponteiro apontando para a primeira posição da lista 1 e o segundo ponteiro apontando para a primeira posição da lista 2.
4. Em seguida, compararemos o valor dos dois ponteiros. O ponteiro com menor valor, copie esse elemento para a Lista 3 e mova o ponteiro para a direita da lista com menor valor e a lista resultante (por exemplo, Lista 1 e Lista 3)
5. Da mesma forma, execute a etapa 4 novamente e novamente.
Travessia adicional …
Nota : Se uma das listas (por exemplo, lista 1 ou lista 2) for totalmente percorrida como no caso, copie todo o conteúdo de outra lista do ponteiro para a lista de resultados (por exemplo, lista 3) da seguinte maneira.
Pseudo-código
Function merge (sublist1, sublist2) (
Create var for result list
While sublist1 length > 0 and sublist2 length > 0
If sublist1(0) < sublist2(0) Copy the sublist1 pointer value to result list and Shift pointer of sublist1 to right
else
Copy the sublist2 pointer value to result list and Shift pointer of sublist2 to right
Return concat sublist1 or sublist2 (depending if node1 is empty or not)
O algoritmo MERGE_SORT divide a lista não classificada em tamanho mínimo e, em seguida, chama o algoritmo MERGE para combinar a lista na nova lista classificada.
Pseudo-código
function mergeSort(list) (
If list length < 2
Return list
Create var for middle index of list
Create var for left index of list
Create var for right index of list
Recursively call mergeSort function
)
Exemplo
Aqui estamos seguindo a implementação descendente de Merge Sort. Começa na parte superior e segue para baixo, com cada turno recursivo fazendo a mesma pergunta "O que é necessário para classificar a lista?" E tendo a resposta é "Divida a lista em duas, faça uma chamada recursiva e mescle o resultados".
Código em Javascript
// Split the list into halves and merge them recursively
function mergeSort (list) (
if (list.length < 2) (
return list;// return once we hit a list with a single element
)
var mid = Math.floor(list.length / 2);
var left = mergeSort(list.slice(0, mid));
var right = mergeSort(list.slice(mid));
return merge(left, right);
)
// compare the lists element by element and return the concatenated resultList
function merge (sublist1, sublist2) (
var resultList = ();
while (sublist1.length > 0 && sublist2.length > 0)
resultList.push(sublist1(0) < sublist2(0)? sublist1.shift() : sublist2.shift());
return resultList.concat(sublist1.length? sublist1 : sublist2);
)
const list = (6, 5, 3, 1, 8, 7, 2, 4, 2, 5, 1, 2, 3) console.log(mergeSort(list)) //( 1, 1, 2, 2, 2, 3, 3, 4, 5, 5, 6, 7, 8 )
A principal função da classificação de mesclagem dividirá a lista fornecida em listas menores em cada iteração da chamada recursiva. Não esqueça que a recursão requer a condição de base para evitar recursões infinitas. No nosso caso, temos:
if (list.length < 2) (
return list;// return once we hit a list with a single element
)
Depois de configurar a condição básica para recursão, identificaremos o índice do meio para dividir a lista fornecida na sub-lista esquerda e direita, como você pode ver acima no diagrama de exemplo. Em seguida, precisamos mesclar a sub-lista esquerda e a sub-lista direita, que examinaremos agora. Na função de mesclagem acima, precisamos garantir que estamos classificando todos os elementos na sub-lista esquerda e na sub-direita Lista. A maneira como faremos isso é usando um loop while. Dentro do loop while, compararemos o elemento na sub-lista esquerda e o elemento na sub-lista direita, um por um. Podemos inserir o menor dos dois na lista de resultados e mover o cursor da sub-lista esquerda e da sub-lista direita de acordo. Finalmente, precisamos concatenar a lista de resultados. Isto é muito importante! Se não fizermos este último passo aqui, teremos uma lista incompleta de elementos no final, porque a condição do loop while falhará assim que qualquer um dos dois ponteiros chegar ao final.
Resultado:
Propriedades da classificação de mesclagem
- A classificação de mesclagem é estável, pois o mesmo elemento em uma matriz mantém suas posições originais uma em relação à outra.
- A classificação de mesclagem não está 'no lugar', pois durante a mesclagem, é criada uma cópia da lista inteira. Devido a isso, a complexidade do espaço (O (n)) desse algoritmo é realmente maior que outros, e não deve ser usada em problemas complexos nos quais o espaço é premium.
- A complexidade geral do tempo da classificação Merge é O (nLogn). É mais eficiente, pois, no pior dos casos, o tempo de execução é O (nlogn).
Conclusão
Mesclar melhor, as piores e as complexidades de tempo médio são as mesmas, o que o torna um algoritmo mais eficiente. Funciona mais rápido que outras técnicas de classificação. A classificação de mesclagem pode ser aplicada a arquivos de qualquer tamanho. É altamente paralelamente devido ao uso do método de dividir e conquistar. Para desenvolver conceitos básicos sólidos em ciência da computação, é aconselhável que você compreenda completamente os diferentes algoritmos de classificação.
Artigo recomendado
Este foi um guia para mesclar classificação em JavaScript. Aqui discutimos a introdução à mesclagem em JavaScript e a implementação, juntamente com as propriedades. Você também pode consultar nossos outros artigos sugeridos para saber mais -
- Funções matemáticas de JavaScript
- Introdução ao JavaScript
- Melhores estruturas Javascript
- Ferramentas JavaScript
- Os 6 principais algoritmos de classificação em JavaScript