A classificação de mesclagem é um algoritmo de classificação baseado na técnica "dividir para conquistar". É um dos algoritmos de classificação mais eficientes.

Neste artigo, você aprenderá sobre o funcionamento do algoritmo de classificação por mesclagem, o algoritmo de classificação por mesclagem, seu complexidade de tempo e espaço, e sua implementação em várias linguagens de programação como C ++, Python e JavaScript.

Como funciona o algoritmo de classificação de mesclagem?

A classificação de mesclagem funciona com o princípio de dividir e conquistar. A classificação por mesclagem divide repetidamente uma matriz em duas submatrizes iguais até que cada submatriz consista em um único elemento. Finalmente, todas essas submatrizes são mescladas de forma que a matriz resultante seja classificada.

Este conceito pode ser explicado de forma mais eficiente com a ajuda de um exemplo. Considere uma matriz não classificada com os seguintes elementos: {16, 12, 15, 13, 19, 17, 11, 18}.

Aqui, o algoritmo de classificação por mesclagem divide a matriz em duas metades, chama a si mesmo para as duas metades e, em seguida, mescla as duas metades classificadas.

instagram viewer

Algoritmo de mesclagem de classificação

Abaixo está o algoritmo de classificação por mesclagem:

MergeSort (arr [], leftIndex, rightIndex)
if leftIndex> = rightIndex
Retorna
senão
Encontre o índice do meio que divide a matriz em duas metades:
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Chame mergeSort () para a primeira metade:
Chame mergeSort (arr, leftIndex, middleIndex)
Chame mergeSort () para a segunda metade:
Chame mergeSort (arr, middleIndex + 1, rightIndex)
Junte as duas metades classificadas nas etapas 2 e 3:
Chamar mesclagem (arr, leftIndex, middleIndex, rightIndex)

Relacionado: O que é recursão e como usá-la?

Complexidade de tempo e espaço do algoritmo de classificação de mesclagem

O algoritmo de classificação Merge pode ser expresso na forma da seguinte relação de recorrência:

T (n) = 2T (n / 2) + O (n)

Depois de resolver essa relação de recorrência usando o teorema do mestre ou o método da árvore de recorrência, você obterá a solução como O (n logn). Assim, a complexidade de tempo do algoritmo de classificação de mesclagem é O (n logn).

O melhor caso de complexidade de tempo da classificação de mesclagem: O (n logn)

A complexidade de tempo médio da classificação de mesclagem: O (n logn)

O pior caso de complexidade de tempo da classificação de mesclagem: O (n logn)

Relacionado: O que é notação Big-O?

A complexidade do espaço auxiliar do algoritmo de classificação de mesclagem é Sobre) como n espaço auxiliar é necessário na implementação de classificação por mesclagem.

Implementação C ++ do Algoritmo de Classificação de Mesclagem

Abaixo está a implementação C ++ do algoritmo de classificação por mesclagem:

// implementação C ++ do
// mesclar algoritmo de classificação
#incluir
usando namespace std;
// Esta função mescla dois subarrays de arr []
// Submatriz à esquerda: arr [leftIndex..middleIndex]
// Submatriz à direita: arr [middleIndex + 1..rightIndex]
void merge (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Criar matrizes temporárias
int L [leftSubarraySize], R [rightSubarraySize];
// Copiando dados para matrizes temporárias L [] e R []
para (int i = 0; i L [i] = arr [leftIndex + i];
para (int j = 0; j R [j] = arr [índice médio + 1 + j];
// Mesclar as matrizes temporárias de volta em arr [leftIndex..rightIndex]
// Índice inicial do subarray esquerdo
int i = 0;
// Índice inicial do subarray direito
int j = 0;
// Índice inicial do subarray mesclado
int k = leftIndex;
while (i {
if (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
senão
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Se houver alguns elementos restantes em L []
// Copiar para arr []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Se houver alguns elementos restantes em R []
// Copiar para arr []
while (j {
arr [k] = R [j];
j ++;
k ++;
}
}
void mergeSort (int arr [], int leftIndex, int rightIndex)
{
if (leftIndex> = rightIndex)
{
Retorna;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
mesclar (arr, leftIndex, middleIndex, rightIndex);
}
// Função para imprimir os elementos
// da matriz
void printArray (int arr [], tamanho int)
{
para (int i = 0; i {
cout << arr [i] << "";
}
cout << endl;
}
// Código do driver
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
tamanho int = sizeof (arr) / sizeof (arr [0]);
cout << "Matriz não classificada:" << endl;
printArray (arr, tamanho);
mergeSort (arr, 0, tamanho - 1);
cout << "Matriz ordenada:" << endl;
printArray (arr, tamanho);
return 0;
}

Resultado:

Matriz não classificada:
16 12 15 13 19 17 11 18
Matriz ordenada:
11 12 13 15 16 17 18 19

Implementação de JavaScript do algoritmo Merge Sort

Abaixo está a implementação JavaScript do algoritmo de classificação por mesclagem:

// implementação de JavaScript do
// mesclar algoritmo de classificação
// Esta função mescla dois subarrays de arr []
// Submatriz à esquerda: arr [leftIndex..middleIndex]
// Submatriz à direita: arr [middleIndex + 1..rightIndex]
function merge (arr, leftIndex, middleIndex, rightIndex) {
deixe leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Criar matrizes temporárias
var L = novo Array (leftSubarraySize);
var R = novo Array (rightSubarraySize);
// Copiando dados para matrizes temporárias L [] e R []
para (deixe i = 0; euL [i] = arr [leftIndex + i];
}
para (seja j = 0; jR [j] = arr [índice médio + 1 + j];
}
// Mesclar as matrizes temporárias de volta em arr [leftIndex..rightIndex]
// Índice inicial do subarray esquerdo
var i = 0;
// Índice inicial do subarray direito
var j = 0;
// Índice inicial do subarray mesclado
var k = leftIndex;
while (i {
if (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
senão
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Se houver alguns elementos restantes em L []
// Copiar para arr []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Se houver alguns elementos restantes em R []
// Copiar para arr []
while (j {
arr [k] = R [j];
j ++;
k ++;
}
}
function mergeSort (arr, leftIndex, rightIndex) {
if (leftIndex> = rightIndex) {
Retorna
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
mesclar (arr, leftIndex, middleIndex, rightIndex);
}
// Função para imprimir os elementos
// da matriz
function printArray (arr, size) {
para (deixe i = 0; eudocument.write (arr [i] + "");
}
document.write ("
");
}
// Código do driver:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var size = arr.length;
document.write ("Matriz não classificada:
");
printArray (arr, tamanho);
mergeSort (arr, 0, tamanho - 1);
document.write ("Matriz ordenada:
");
printArray (arr, tamanho);

Resultado:

Matriz não classificada:
16 12 15 13 19 17 11 18
Matriz ordenada:
11 12 13 15 16 17 18 19

Relacionado: Programação dinâmica: exemplos, problemas comuns e soluções

Implementação Python do algoritmo Merge Sort

Abaixo está a implementação Python do algoritmo de classificação por mesclagem:

# Implementação Python do
# algoritmo de classificação de mesclagem
def mergeSort (arr):
se len (arr)> 1:
# Encontrando o índice do meio da matriz
middleIndex = len (arr) // 2
# Metade esquerda da matriz
L = arr [: middleIndex]
# Metade direita da matriz
R = arr [middleIndex:]
# Classificando a primeira metade da matriz
mergeSort (L)
# Classificando a segunda metade da matriz
mergeSort (R)
# Índice inicial do subarray esquerdo
i = 0
# Índice inicial do subarray direito
j = 0
# Índice inicial da submatriz mesclada
k = 0
# Copiar dados para matrizes temporárias L [] e R []
enquanto i se L [i] arr [k] = L [i]
i = i + 1
senão:
arr [k] = R [j]
j = j + 1
k = k + 1
# Verificar se existem alguns elementos restantes
enquanto i arr [k] = L [i]
i = i + 1
k = k + 1
enquanto j arr [k] = R [j]
j = j + 1
k = k + 1
# Função para imprimir os elementos
# da matriz
def printArray (arr, tamanho):
para i no intervalo (tamanho):
imprimir (arr [i], fim = "")
impressão()
# Código do driver
arr = [16, 12, 15, 13, 19, 17, 11, 18]
tamanho = len (arr)
print ("Matriz não classificada:")
printArray (arr, tamanho)
mergeSort (arr)
imprimir ("Matriz classificada:")
printArray (arr, tamanho)

Resultado:

Matriz não classificada:
16 12 15 13 19 17 11 18
Matriz ordenada:
11 12 13 15 16 17 18 19

Compreender outros algoritmos de classificação

A classificação é um dos algoritmos mais usados ​​na programação. Você pode classificar os elementos em diferentes linguagens de programação usando vários algoritmos de classificação, como classificação rápida, classificação por bolha, classificação por mesclagem, classificação por inserção, etc.

A classificação por bolha é a melhor escolha se você deseja aprender sobre o algoritmo de classificação mais simples.

E-mail
Uma introdução ao algoritmo de classificação de bolhas

O algoritmo Bubble Sort: uma excelente introdução à classificação de matrizes.

Leia a seguir

Tópicos relacionados
  • Programação
  • JavaScript
  • Pitão
  • Tutoriais de codificação
Sobre o autor
Yuvraj Chandra (27 artigos publicados)

Yuvraj é estudante de graduação em Ciência da Computação na Universidade de Delhi, na Índia. Ele é apaixonado por Full Stack Web Development. Quando não está escrevendo, ele está explorando a profundidade de diferentes tecnologias.

Mais de Yuvraj Chandra

Assine a nossa newsletter

Junte-se ao nosso boletim informativo para dicas de tecnologia, análises, e-books grátis e ofertas exclusivas!

Mais um passo…!

Confirme o seu endereço de e-mail no e-mail que acabamos de enviar.

.