Tabla de contenido
- Introducción
- ¿Qué es Merge Sort en C++?
- Enfoque divide y vencerás
- Algoritmo de clasificación por fusión
- Implementación de Merge Sort en C++
- Conclusión
1. Introducción
Los algoritmos de clasificación en informática se utilizan para organizar los datos en orden ascendente o descendente. Hay varios algoritmos de clasificación con distintas propiedades disponibles. Merge sort es uno de los métodos en C++ que puede ordenar las matrices.
2. ¿Qué es Merge Sort en C++?
La ordenación por combinación utiliza la técnica divide y vencerás que puede organizar los elementos de una matriz. También puede ordenar la lista de elementos en C++. Divide la entrada en dos mitades, ordena cada mitad de forma independiente y luego las fusiona en el orden correcto.
3. Enfoque divide y vencerás
El algoritmo de clasificación aplica una estrategia de divide y vencerás, que implica dividir la matriz de entrada en subarreglos más pequeños, resolverlos por separado y luego fusionar los resultados para producir una salida ordenada. En el caso del ordenamiento por fusión, la matriz se divide recursivamente en dos mitades hasta que solo queda un elemento en cada mitad.
4. Algoritmo de clasificación por fusión
El algoritmo de clasificación por fusión consta de dos pasos principales: dividir y fusionar. Los pasos son los siguientes:
4.1 Dividir
El algoritmo de clasificación por fusión sigue una estrategia de divide y vencerás para clasificar elementos en una matriz.
- El primer paso en el algoritmo verificará los elementos de la matriz. Si contiene un elemento, ya se considera ordenado y el algoritmo devolverá la misma matriz sin ningún cambio.
- Si el arreglo contiene más de un elemento, el algoritmo procede a dividirlo en dos mitades: la mitad izquierda y la mitad derecha.
- Luego, el algoritmo de clasificación por combinación se aplica recursivamente a las mitades izquierda y derecha de la matriz, dividiéndolas efectivamente en subarreglos más pequeños y clasificándolas individualmente.
- Este proceso recursivo continúa hasta que los subarreglos contienen solo un elemento cada uno (según el paso 1), momento en el que se pueden fusionar para producir un arreglo de salida ordenado final.
4.2 Fusionar
Ahora veremos los pasos para fusionar los arreglos:
- El primer paso para el algoritmo de clasificación por fusión consiste en crear una matriz vacía.
- Luego, el algoritmo procede a comparar los primeros elementos de las mitades izquierda y derecha de la matriz de entrada.
- El más pequeño de los dos elementos se agrega a la nueva matriz y luego se elimina de su mitad respectiva de la matriz de entrada.
- Luego se repiten los pasos 2-3 hasta que se vacía una de las mitades.
- Cualquier elemento restante en la mitad no vacía se agrega a la nueva matriz.
- La matriz resultante ahora está completamente ordenada y representa el resultado final del algoritmo de ordenación por fusión.
5. Implementación de Merge Sort en C++
Para implementar la ordenación por fusión en C++, se siguen dos métodos diferentes. La complejidad temporal de ambos métodos es equivalente, pero el uso de subarreglos temporales difiere.
El primer método para el ordenamiento por fusión en C++ usa dos subarreglos temporales, mientras que el segundo usa solo uno. Vale la pena señalar que el tamaño total de los dos subarreglos temporales en el primer método es igual al tamaño del arreglo original en el segundo método, por lo que la complejidad del espacio permanece constante.
Método 1: uso de dos subarreglos temporales
Aquí hay un programa de ejemplo para ordenar por fusión en C++ usando el Método 1, que usa dos subarreglos temporales:
#incluirusando el espacio de nombres estándar ;
vacío unir ( En t Arr [ ] , En t yo , En t metro , En t r )
{
En t n1 = metro - yo + 1 ;
En t n2 = r - metro ;
En t L [ n1 ] , R [ n2 ] ;
para ( En t i = 0 ; i < n1 ; i ++ )
L [ i ] = Arr [ yo + i ] ;
para ( En t j = 0 ; j < n2 ; j ++ )
R [ j ] = Arr [ metro + 1 + j ] ;
En t i = 0 , j = 0 , k = yo ;
mientras ( i < n1 && j < n2 ) {
si ( L [ i ] <= R [ j ] ) {
Arr [ k ] = L [ i ] ;
i ++;
}
demás {
Arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
mientras ( i < n1 ) {
Arr [ k ] = L [ i ] ;
i ++;
k ++;
}
mientras ( j < n2 ) {
Arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
vacío combinarOrdenar ( En t Arr [ ] , En t yo , En t r )
{
si ( yo < r ) {
En t metro = yo + ( r - yo ) / 2 ;
combinarOrdenar ( Arr , yo , metro ) ;
combinarOrdenar ( Arr , metro + 1 , r ) ;
unir ( Arr , yo , metro , r ) ;
}
}
En t principal ( )
{
En t Arr [ ] = { 12 , 11 , 13 , 5 , 6 , 7 } ;
En t arr_size = tamaño de ( Arr ) / tamaño de ( Arr [ 0 ] ) ;
cout << 'La matriz dada es \norte ' ;
para ( En t i = 0 ; i < arr_size ; i ++ )
cout << Arr [ i ] << ' ' ;
combinarOrdenar ( Arr , 0 , arr_size - 1 ) ;
cout << ' \norte La matriz ordenada es \norte ' ;
para ( En t i = 0 ; i < arr_size ; i ++ )
cout << Arr [ i ] << ' ' ;
devolver 0 ;
}
En este programa, la función de combinación toma tres argumentos arr, l y r, que representan la matriz que se ordenará y muestra los índices de la subarreglo que se debe combinar. La función primero encuentra los tamaños de los dos subarreglos que se fusionarán, luego crea dos subarreglos temporales L y R para almacenar los elementos de estos subarreglos. Luego compara los elementos en L y R y los fusiona en la matriz original llamada Arr en orden ascendente.
La técnica divide y vencerás es empleada por la función mergeSort para dividir la matriz en dos mitades recursivamente hasta que solo quede un elemento en la subarreglo. Luego fusiona los dos subarreglos en un subarreglo ordenado. La función continúa fusionando los subarreglos a menos que clasifique el arreglo completo.
En la función principal, definimos una matriz arr con 6 elementos y llamamos a la función mergeSort para ordenarla. Al final del código, se imprime la matriz ordenada.
Método 2: usar un subarreglo temporal
Aquí hay un programa de ejemplo para ordenar por fusión en C++ usando el Método 2, que usa un único subarreglo temporal:
#incluirusando el espacio de nombres estándar ;
vacío unir ( En t Arr [ ] , En t yo , En t metro , En t r )
{
En t i , j , k ;
En t n1 = metro - yo + 1 ;
En t n2 = r - metro ;
// Crear subarreglos temporales
En t L [ n1 ] , R [ n2 ] ;
// Copiar datos a subarreglos
para ( i = 0 ; i < n1 ; i ++ )
L [ i ] = Arr [ yo + i ] ;
para ( j = 0 ; j < n2 ; j ++ )
R [ j ] = Arr [ metro + 1 + j ] ;
// Combinar los subarreglos temporales de nuevo en el arreglo original
i = 0 ;
j = 0 ;
k = yo ;
mientras ( i < n1 && j < n2 ) {
si ( L [ i ] <= R [ j ] ) {
Arr [ k ] = L [ i ] ;
i ++;
}
demás {
Arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
// Copia los elementos restantes de L[]
mientras ( i < n1 ) {
Arr [ k ] = L [ i ] ;
i ++;
k ++;
}
// Copia los elementos restantes de R[]
mientras ( j < n2 ) {
Arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
vacío combinarOrdenar ( En t Arr [ ] , En t yo , En t r )
{
si ( yo < r ) {
En t metro = yo + ( r - yo ) / 2 ;
// Ordenar las mitades izquierda y derecha recursivamente
combinarOrdenar ( Arr , yo , metro ) ;
combinarOrdenar ( Arr , metro + 1 , r ) ;
// Combinar las dos mitades ordenadas
unir ( Arr , yo , metro , r ) ;
}
}
En t principal ( )
{
En t Arr [ ] = { 12 , 11 , 13 , 5 , 6 , 7 } ;
En t arr_size = tamaño de ( Arr ) / tamaño de ( Arr [ 0 ] ) ;
cout << 'La matriz dada es \norte ' ;
para ( En t i = 0 ; i < arr_size ; i ++ )
cout << Arr [ i ] << ' ' ;
combinarOrdenar ( Arr , 0 , arr_size - 1 ) ;
cout << ' \norte La matriz ordenada es \norte ' ;
para ( En t i = 0 ; i < arr_size ; i ++ )
cout << Arr [ i ] << ' ' ;
devolver 0 ;
}
Este programa es como el anterior, pero en lugar de usar dos subarreglos temporales L y R, usa un único subarreglo temporal temp. La función de combinación funciona de la misma manera que antes, pero en lugar de copiar los datos a L y R, los copia a temp. Luego fusiona los elementos de la matriz temporal de nuevo en el Arr que es la matriz original.
La función mergeSort es la misma que antes, excepto que usa temp en lugar de L y R para almacenar el subarreglo temporal.
En la función principal, definimos una matriz arr con 6 elementos y llamamos a la función mergeSort para ordenarla. La ejecución del código finaliza imprimiendo la matriz ordenada en la pantalla.
Conclusión
Merge sort es un algoritmo que ordena los elementos de la matriz y utiliza la técnica divide y vencerás y hace comparaciones entre los elementos. Merge sort en C++ tiene una complejidad de tiempo de O(n log n) y es particularmente efectivo para clasificar arreglos grandes. Aunque requiere memoria adicional para almacenar los subarreglos fusionados, su estabilidad lo convierte en una opción popular para ordenar.