Fusionar algoritmo de clasificación usando Python

En este artículo, vamos a aprender sobre un algoritmo de clasificación de fusión. Merge Sort es un método popular de clasificación de división y conclusión. La clasificación de fusión se usa ampliamente debido a su velocidad en la clasificación de los datos. Es una de las mejores ilustraciones de cómo dividir y conquistar algoritmos que se pueden usar en la práctica. Fusionar Sort separa una lista de datos en dos mitades y luego llama a estas subpartas para dividirlos en dos mitades. Repita la operación hasta que cada componente de la lista tenga un solo elemento. Al clasificar estas subpartas de un elemento en dos componentes, luego los fusionará. Después de clasificar, la subparte de dos elementos se vinculará con los otros dos componentes. Este procedimiento se repite hasta que se obtenga la lista final de elementos ordenados invocando la función repetidamente.

La ilustración básica del tipo de fusión se da en el siguiente ejemplo:

Código de Python: El siguiente código de Python es para el algoritmo de clasificación de fusión:

Def Merge_sort (UnsortedList):
Si Len (UnsortedList)> 1:
Mid = Len (UnsortedList) // 2
LeftList = UnsortedList [: Mid]
RightList = UnsortedList [Mid:]
# Llamada recursiva Cuando vamos dos Listas (izquierda y derecha) para clasificar
Merge_sort (LeftList)
Merge_sort (lista de rectas)
# Porque tenemos dos listas, por lo que necesitamos a los iteradores para la iteración de cada lista
M = 0
n = 0
# Necesitamos un iterador común que itera a la lista principal
z = 0
mientras que m < len(leftList) and n < len(rightList):
Si LeftList [M] <= rightList[n]:
# Aquí estamos usando los primeros elementos laterales izquierdos
UnsortedList [Z] = LeftList [M]
# Incrementa el iterador principal
m += 1
demás:
UnsortedList [Z] = Lista derecha [N]
n += 1
z += 1
# Si los valores se dejan en la lista, entonces procesamos aquí
mientras que m < len(leftList):
UnsortedList [Z] = LeftList [M]
m += 1
z += 1
Mientras que n < len(rightList):
UnsortedList [Z] = Lista derecha [N]
n += 1
z += 1
UnsortedList = [23,56,0,23,85,100,200,12,32,78,90,102]
Merge_sort (UnsortedList)
Impresión (UnsortedList)

Producción:

[0, 12, 23, 23, 32, 56, 78, 85, 90, 100, 102, 200]

Esta es la forma recursiva de fusionar la implementación de clasificación. Estos son los siguientes pasos para obtener la matriz ordenada utilizando este método:

• Línea 1: Definimos una función (fusion_sort) cuando necesitamos ordenar una lista de elementos sin clasificar. Ahora, vamos a explicar todas las líneas de esta función de fusión_sort.
• Línea 2-5: Lo primero que estamos revisando es si los elementos de la lista no organizados tienen más de 1 elemento o no. Si solo hay un elemento, no hay necesidad de clasificar. Entonces, estamos revisando esta primera condición.

  Si los elementos son más de 1, entonces estamos tratando de obtener el valor medio de la lista para dividir toda la lista en dos partes (izquierda y derecha) para una llamada recursiva adicional. Cada llamada recursiva divide la lista hacia la izquierda y hacia la derecha hasta que se adquieren dos entradas adyacentes.

• Línea 8-9: Llamamos a la clasificación de fusión de manera recursiva para cada sublista (izquierda y derecha).
• Línea 11-15: El procedimiento de clasificación ahora comienza. Cada uno llama a dos partes atravesadas por los iteradores M y N. El iterador Z itera en todas las listas, haciendo modificaciones a medida que avanza.
• Línea 17-26: LeftList [M] se asigna a la ranura de la lista antihorable [z], y M se incrementa si el valor en M es menor que el valor en n. Si no, se selecciona la lista correcta [n]. Todos los valores asignados a Z están ordenados.
• Línea 29-37: Al final de este bucle, una de las partes puede no haberse cruzado por completo. Su contenido se asigna a las posiciones restantes en la lista.

Complejidad del tiempo:

La complejidad del tiempo de la clasificación de fusión depende de dos factores:

• El factor dividido de la lista que toma el registro (n)
• El segundo factor fusiona la lista de dos, que lleva tiempo lineal, por lo que su complejidad es o (n)

Por lo tanto, la complejidad total se basa en los dos factores anteriores del tipo de fusión es o (n.logn).

Ventajas del algoritmo de clasificación de fusión:

• Fusionar la clasificación hace que sea simple clasificar los conjuntos de big data.
• Fusionar sort puede acceder a los datos en orden, por lo tanto, no se requiere acceso aleatorio.
• Fusion Sort es un método de clasificación confiable.

Desventajas del algoritmo de clasificación de fusión:

• El tipo de fusión requiere una matriz de tamaño similar para ordenar la lista, que es una desventaja del uso de la memoria.
• Al clasificar los conjuntos de datos más pequeños, lleva más tiempo.

Conclusión:

La clasificación de fusión es un método de clasificación rápida y versátil. Su beneficio clave es el tiempo de ejecución y eficiencia constantes del algoritmo mientras se clasifica grandes matrices. En comparación con el tipo rápido, no se basa en ningún juicio defectuoso que resulte en largos tiempos de ejecución. El tipo de fusión es el mejor algoritmo para ordenar los elementos. Sin embargo, el principal inconveniente del tipo de fusión es que usa mucha memoria antes de fusionar los elementos. También es muy útil para la futura ingeniería de software, donde pueden construir más algoritmos de clasificación basados ​​en el método dividido y conquistador.

Vimos el ejemplo estándar del tipo de fusión sin codificar primero para comprender cómo funciona esta analogía, y luego implementamos pasos similares en la programación de Python. Ahora, somos conscientes de la tecnología de división y conquistar del tipo de fusión. Esperamos que hayas encontrado este artículo útil. Consulte Linux Sugerencia para obtener más consejos e información.