Introducción al algoritmo de clasificación por fusión

Merge sort es un algoritmo de clasificación basado en la técnica "divide y vencerás". Es uno de los algoritmos de clasificación más eficientes.

En este artículo, aprenderá sobre el funcionamiento del algoritmo de clasificación de fusión, el algoritmo de clasificación de fusión, su la complejidad del tiempo y el espacio, y su implementación en varios lenguajes de programación como C ++, Python y JavaScript.

¿Cómo funciona el algoritmo de clasificación por fusión?

Merge sort funciona según el principio de divide y vencerás. Merge sort divide repetidamente una matriz en dos subarreglos iguales hasta que cada subarreglo consta de un solo elemento. Finalmente, todos esos subarreglos se combinan de manera que se ordena el arreglo resultante.

Este concepto se puede explicar de manera más eficiente con la ayuda de un ejemplo. Considere una matriz sin clasificar con los siguientes elementos: {16, 12, 15, 13, 19, 17, 11, 18}.

Aquí, el algoritmo de clasificación de combinación divide la matriz en dos mitades, se llama a sí mismo para las dos mitades y luego fusiona las dos mitades ordenadas.

Combinar algoritmo de ordenación

A continuación se muestra el algoritmo del tipo de combinación:

MergeSort (arr [], leftIndex, rightIndex)
if leftIndex> = rightIndex
regreso
demás
Encuentre el índice medio que divide la matriz en dos mitades: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Llame a mergeSort () para la primera mitad: 
Llamar mergeSort (arr, leftIndex, middleIndex)
Llame a mergeSort () para la segunda mitad:
Llamar mergeSort (arr, middleIndex + 1, rightIndex)
Combine las dos mitades ordenadas en el paso 2 y 3:
Combinación de llamadas (arr, leftIndex, middleIndex, rightIndex)

Relacionados: ¿Qué es la recursividad y cómo se usa?

Complejidad temporal y espacial del algoritmo de clasificación por fusión

El algoritmo de clasificación Merge se puede expresar en forma de la siguiente relación de recurrencia:

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

Después de resolver esta relación de recurrencia utilizando el teorema del maestro o el método del árbol de recurrencia, obtendrá la solución como O (n logn). Por lo tanto, la complejidad de tiempo del algoritmo de clasificación de combinación es O (n logn).

La complejidad de tiempo en el mejor de los casos del tipo de combinación: O (n logn)

La complejidad del tiempo de caso promedio del tipo de combinación: O (n logn)

La complejidad de tiempo del peor de los casos del tipo de combinación: O (n logn)

Relacionados: ¿Qué es la notación Big-O?

La complejidad del espacio auxiliar del algoritmo de clasificación de combinación es En) como norte Se requiere espacio auxiliar en la implementación de ordenación de combinación.

Implementación en C ++ del algoritmo de clasificación por fusión

A continuación se muestra la implementación de C ++ del algoritmo de ordenación por combinación:

// Implementación en C ++ del
// fusionar algoritmo de ordenación
#incluir 
usando el espacio de nombres std;
// Esta función fusiona dos subarreglos de arr []
// Subarreglo izquierdo: arr [leftIndex..middleIndex]
// Subarreglo derecho: arr [middleIndex + 1..rightIndex]
combinación vacía (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Crea matrices temporales
int L [leftSubarraySize], R [rightSubarraySize];
// Copiando datos a matrices temporales L [] y R []
para (int i = 0; i L [i] = arr [leftIndex + i];
para (int j = 0; j R [j] = arr [middleIndex + 1 + j];
// Fusionar las matrices temporales de nuevo en arr [leftIndex..rightIndex]
// Índice inicial del subarreglo izquierdo
int i = 0;
// Índice inicial del subarreglo derecho
int j = 0;
// Índice inicial del subarreglo combinado
int k = leftIndex;
while (i {
si (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
demás
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Si quedan algunos elementos en L []
// Copiar a arr []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Si quedan algunos elementos en R []
// Copiar a arr []
while (j {
arr [k] = R [j];
j ++;
k ++;
}
}
void mergeSort (int arr [], int leftIndex, int rightIndex)
{
if (leftIndex> = rightIndex)
{
regreso;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
merge (arr, leftIndex, middleIndex, rightIndex);
}
// Función para imprimir los elementos
// de la matriz
void printArray (int arr [], int tamaño)
{
para (int i = 0; i {
cout << arr [i] << "";
}
cout << endl;
}
// Código del controlador
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int tamaño = tamaño de (arr) / tamaño de (arr [0]);
cout << "Matriz sin clasificar:" << endl;
printArray (arr, tamaño);
mergeSort (arr, 0, tamaño - 1);
cout << "Matriz ordenada:" << endl;
printArray (arr, tamaño);
return 0;
}

Producción:

Matriz sin clasificar:
16 12 15 13 19 17 11 18 
Matriz ordenada:
11 12 13 15 16 17 18 19

Implementación de JavaScript del algoritmo de ordenación por fusión

A continuación se muestra la implementación de JavaScript del algoritmo de ordenación por combinación:

// Implementación JavaScript del
// fusionar algoritmo de ordenación
// Esta función fusiona dos subarreglos de arr []
// Subarreglo izquierdo: arr [leftIndex..middleIndex]
// Subarreglo derecho: arr [middleIndex + 1..rightIndex]
función merge (arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Crea matrices temporales
var L = new Array (leftSubarraySize);
var R = new Array (rightSubarraySize);
// Copiando datos a matrices temporales L [] y R []
para (sea i = 0; IL [i] = arr [leftIndex + i];
}
para (sea j = 0; jR [j] = arr [middleIndex + 1 + j];
}
// Fusionar las matrices temporales de nuevo en arr [leftIndex..rightIndex]
// Índice inicial del subarreglo izquierdo
var i = 0;
// Índice inicial del subarreglo derecho
var j = 0;
// Índice inicial del subarreglo combinado
var k = leftIndex;
while (i {
si (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
demás
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Si quedan algunos elementos en L []
// Copiar a arr []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Si quedan algunos elementos en R []
// Copiar a arr []
while (j {
arr [k] = R [j];
j ++;
k ++;
}
}
function mergeSort (arr, leftIndex, rightIndex) {
if (leftIndex> = rightIndex) {
regreso
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
merge (arr, leftIndex, middleIndex, rightIndex);
}
// Función para imprimir los elementos
// de la matriz
function printArray (arr, size) {
para (sea i = 0; Idocument.write (arr [i] + "");
}
document.write ("
");
}
// Código del controlador:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var tamaño = longitud de arr.;
document.write ("Matriz sin clasificar:
");
printArray (arr, tamaño);
mergeSort (arr, 0, tamaño - 1);
document.write ("Matriz ordenada:
");
printArray (arr, tamaño);

Producción:

Matriz sin clasificar:
16 12 15 13 19 17 11 18
Matriz ordenada:
11 12 13 15 16 17 18 19

Relacionados: Programación dinámica: ejemplos, problemas comunes y soluciones

Implementación en Python del algoritmo de clasificación por fusión

A continuación se muestra la implementación de Python del algoritmo de clasificación de combinación:

# Implementación en Python del
# fusionar algoritmo de ordenación
def mergeSort (arr):
si len (arr)> 1:
# Encontrar el índice medio de la matriz
middleIndex = len (arr) // 2
# Mitad izquierda de la matriz
L = arr [: middleIndex]
# Mitad derecha de la matriz
R = arr [middleIndex:]
# Ordenando la primera mitad de la matriz
mergeSort (L)
# Ordenando la segunda mitad de la matriz
mergeSort (R)
# Índice inicial del subarreglo izquierdo
i = 0
# Índice inicial del subarreglo derecho
j = 0
# Índice inicial del subarreglo combinado
k = 0
# Copiar datos en matrices temporales L [] y R []
mientras que i si L [i] arr [k] = L [i]
yo = yo + 1
demás:
arr [k] = R [j]
j = j + 1
k = k + 1
# Comprobando si quedan algunos elementos
mientras que yo arr [k] = L [i]
yo = yo + 1
k = k + 1
mientras que j arr [k] = R [j]
j = j + 1
k = k + 1
# Función para imprimir los elementos
# de la matriz
def printArray (arr, tamaño):
para i en rango (tamaño):
print (arr [i], end = "")
impresión()
# Código del conductor
arr = [16, 12, 15, 13, 19, 17, 11, 18]
tamaño = len (arr)
print ("Matriz sin clasificar:")
printArray (arr, tamaño)
mergeSort (arr)
print ("Matriz ordenada:")
printArray (arr, tamaño)

Producción:

Matriz sin clasificar:
16 12 15 13 19 17 11 18
Matriz ordenada:
11 12 13 15 16 17 18 19

Comprender otros algoritmos de clasificación

La clasificación es uno de los algoritmos más utilizados en programación. Puede ordenar elementos en diferentes lenguajes de programación utilizando varios algoritmos de clasificación como clasificación rápida, clasificación de burbujas, clasificación de combinación, clasificación de inserción, etc.

La clasificación de burbujas es la mejor opción si desea aprender sobre el algoritmo de clasificación más simple.

Introducción al algoritmo de clasificación de burbujas

El algoritmo Bubble Sort: una excelente introducción a la ordenación de matrices.

Leer siguiente

Sobre el Autor