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.
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.
O algoritmo Bubble Sort: uma excelente introdução à classificação de matrizes.
Leia a seguir
- Programação
- JavaScript
- Pitão
- Tutoriais de codificação
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.
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.