Este blog se basa en el enfoque de divide y vencerás. Merge Sort es un algoritmo de 'divide y vencerás' en el que el problema se divide en subproblemas y luego se fusiona para conquistar la solución. Este blog sobre Merge Sort in lo guiará a través de los temas a continuación en detalle:
- ¿Qué es Merge Sort en Python?
- El enfoque Divide and Conquer
- Implementando Merge Sort en Python
- Diagrama de flujo para la implementación de Merge Sort
- Ventajas y uso
¿Qué es Merge Sort en Python?
Merge Sort se basa en el algoritmo de dividir y conquistar, donde la matriz de entrada se divide en dos mitades, luego se ordena por separado y se fusiona nuevamente para llegar a la solución. La función merge () se utiliza para fusionar el ordenado .
El enfoque Divide and Conquer
- La matriz se divide por la mitad y el proceso se repite con cada mitad hasta que cada mitad tenga un tamaño de 1 o 0.
- La matriz de tamaño 1 se ordena trivialmente.
- Ahora, las dos matrices ordenadas se combinan en una gran matriz. Y esto continúa hasta que se combinan todos los elementos y se ordena la matriz.
A continuación, se muestra una visualización del ordenamiento combinado para aclarar la imagen.
Matriz de entrada = [3,1,4,1,5,9,2,6,5,4]
curriculum vitae desarrollador de front-end java
Ahora, pasemos a la implementación.
Implementando Merge Sort en Python
def mergeSort (nlist): print ('Splitting', nlist) if len (nlist)> 1: mid = len (nlist) // 2 lefthalf = nlist [: mid] righthalf = nlist [mid:] mergeSort (lefthalf) mergeSort (mitad derecha) i = j = k = 0 mientras yo Salida:
$ python main.py
('División', [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
('Dividir', [3, 1, 4, 1, 5])
('Dividir', [3, 1])
('Dividir', [3])
('Fusión', [3])
('Dividir', [1])
('Fusión', [1])
('Fusión', [1, 3])
('Dividir', [4, 1, 5])
('Dividir', [4])
('Fusión', [4])
('Dividir', [1, 5])
('Dividir', [1])
('Fusión', [1])
('Dividir', [5])
('Fusión', [5])
('Fusión', [1, 5])
('Fusión', [1, 4, 5])
('Fusión', [1, 1, 3, 4, 5])
('Dividir', [9, 2, 6, 5, 4])
('Dividir', [9, 2])
('Dividir', [9])
('Fusión', [9])
('Dividir', [2])
('Fusión', [2])
('Fusión', [2, 9])
('Dividir', [6, 5, 4])
('Dividir', [6])
('Fusión', [6])
('Dividir', [5, 4])
('Dividir', [5])
('Fusión', [5])
('Dividir', [4])
('Fusión', [4])
('Fusión', [4, 5])
('Fusión', [4, 5, 6])
('Fusión', [2, 4, 5, 6, 9])
('Fusión', [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]
que es un metodo virtual
Diagrama de flujo para la implementación de Merge Sort
Ventajas y uso del ordenamiento combinado
La mayoría de los otros algoritmos funcionan mal con estructuras de datos secuenciales como archivos y listas enlazadas. En estas estructuras, acceder a un elemento aleatorio requiere un tiempo lineal, no un tiempo constante regular. Y la naturaleza del tipo de combinación hace que sea fácil y rápido para tales estructuras de datos.Una de las mejores características del ordenamiento por combinación es su bajo número de comparaciones. Hace O (n * log (n)) número de comparaciones, pero el factor constante es bueno en comparación con el ordenamiento rápido, lo que lo hace útil cuando la función de comparación es una operación lenta.Además, el enfoque de dividir y conquistar del ordenamiento por combinación lo hace conveniente para el procesamiento en paralelo.
Con esto, llegamos al final de este blog sobre “Cómo implementar Merge Sort en Python”. Espero que el contenido agregue algún valor a su conocimiento en Python. Para obtener un conocimiento profundo de Python junto con sus diversas aplicaciones, puede inscribirse en Live con soporte 24/7 y acceso de por vida.