Cualquier ejecución de MergeSort se puede visualizar como un árbol. Las hojas del árbol son los elementos individuales de la matriz. Cada nodo interno del árbol corresponde a la fusión de dos matrices más pequeñas en una matriz más grande.
Árbol de muestra MergeSort:
abcdefgh
/ \
adgh bcef
/ \ / \
gh ad bf ce
/ \ / \ / \ / \
hgdabfce
- ¿Puedes ser bueno en la programación pero malo en los algoritmos?
- ¿Qué algoritmos y estructuras de datos se pueden usar para encontrar anagramas?
- Quicksort: ¿Cuál es el algoritmo de ordenación rápida?
- Cómo usar el código VHDL para generar el seno de un ángulo dado usando el algoritmo CORDIC
- ¿Hay algún problema para el cual se pruebe que no existe un algoritmo óptimo?
La implementación de arriba hacia abajo es la implementación que utiliza la recursividad. Comienza en la parte superior del árbol y continúa hacia abajo , cada vez que hace la misma pregunta (¿qué debo hacer para ordenar esta matriz?) Y la responde (divídala en dos, haga llamadas recursivas, combine resultados), hasta que llegar al pie del árbol.
La implementación ascendente no utiliza la recursividad. Comienza directamente en la parte inferior del árbol y continúa hacia arriba iterando sobre las piezas y fusionándolas.
A continuación se muestra una implementación de muestra de una posible versión ascendente. Tenemos una cola Q. Al principio, Q contiene secuencias de un elemento [matemáticas] n [/ matemáticas]. Durante la ordenación, repetidamente tomamos las dos secuencias más cortas, las fusionamos e insertamos la nueva secuencia en la cola.
de colecciones importación deque
def fusionar (X, Y):
X, Y, Z = deque (X), deque (Y), []
mientras que len (X)> 0 y len (Y)> 0:
si X [0] <Y [0]: Z.append (X.popleft ())
más: Z.append (Y.popleft ())
volver Z + lista (X) + lista (Y)
def bottom_up_mergesort (A):
si len (A) <= 1: lista de retorno (A)
Q = deque ([a] para a en A)
mientras cierto:
X = Q.popleft ()
si len (Q) == 0: devuelve X
Y = Q.popleft ()
# intente habilitar esta salida de depuración:
# print (‘fusión’, X, ‘y’, Y)
Q.append (fusionar (X, Y))
print (bottom_up_mergesort (‘abracadabra’))
