Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 1
Lección 8: Ordenamiento por mezclaMezcla en tiempo lineal
La parte restante del ordenamiento por mezcla es la función
merge
, la cual mezcla dos subarreglos ordenados adyacentes, array[p..q]
y array[q+1..r]
, en un solo subarreglo ordenado en array[p..r]
. Vamos a ver cómo construir esta función para que sea lo más eficiente posible. Digamos que los dos subarreglos tienen un total de n elementos. Tenemos que examinar cada uno de los elementos para poder mezclarlos, así que lo mejor que podemos esperar sería un tiempo de mezcla de \Theta, left parenthesis, n, right parenthesis. De hecho, veremos cómo combinar un total de n elementos en un tiempo \Theta, left parenthesis, n, right parenthesis.Para poder mezclar los subarreglos ordenados
array[p..q]
y array [q+1..r]
y tener el resultado en array[p..r]
, primero tenemos que hacer arreglos temporales y copiar array[p..q]
y array[q+1..r]
en estos arreglos temporales. No podemos escribir sobre las posiciones en array[p..r]
hasta no tener los elementos que originalmente estaban en array[p..q]
y array [q+1..r]
copiados de forma segura.Entonces, lo primero que hay que hacer en la función
merge
, es asignar dos arreglos temporales, lowHalf
y highHalf
, para copiar todos los elementos de array[p..q]
en lowHalf
, y todos los de array[q+1..r]
en highHalf
. ¿Qué tan grande debe ser lowHalf
? El subarreglo array[p..q]
contiene q, minus, p, plus, 1 elementos. ¿Qué hay de highHalf
? El subarreglo array[q+1..r]
contiene r, minus, q elementos. (En JavaScript no tenemos que dar el tamaño de un arreglo cuando lo creamos, pero como sí tenemos que hacerlo en muchos otros lenguajes de programación, a menudo lo consideramos cuando describimos un algoritmo).En nuestro arreglo de ejemplo, [14, 7, 3, 12, 9, 11, 6, 2], las cosas se ven así después de haber ordenado de manera recursiva
array[0..3]
y array[4..7]
(de modo que p, equals, 0, q, equals, 3 y r, equals, 7) y después de haber copiado estos subarreglos en lowHalf
y highHalf
:Los números en
array
están atenuados para indicar que aunque estas posiciones en el arreglo contienen valores, los valores "reales" están ahora en lowHalf
y highHalf
. Ahora podemos volver a escribir los números atenuados a voluntad.A continuación, mezclamos los dos subarreglos ordenados, que ahora están en
lowHalf
y highHalf
, de regreso en array[p..r]
. Deberíamos poner el valor más pequeño en cualquiera de los dos subarreglos en array[p]
. ¿Dónde podría estar este valor más pequeño? Como los subarreglos están ordenados, el valor más pequeño debe estar en uno de dos lugares: en lowHalf[0]
o en highHalf[0]
(es posible que el mismo valor esté en ambos lados, y entonces podemos llamar a cualquiera de los dos el valor más pequeño). Con solo una comparación podemos determinar si copiar lowHalf[0]
o highHalf[0]
en array[p]
. En nuestro ejemplo, highHalf[0]
fue más pequeño. También vamos a establecer tres variables para indexar los arreglos:i
indexa el siguiente elemento delowHalf
que no hemos copiado de regreso enarray
. Inicialmente,i
es 0.j
indexa el siguiente elemento dehighHalf
que no hemos copiado de regreso enarray
. Inicialmente,j
es 0.k
indexa la siguiente ubicación enarray
en la cual copiamos. Inicialmente,k
es igual ap
.
Después de que copiamos de
lowHalf
o de highHalf
a array
, debemos incrementar (sumarle 1 a) k
de modo que copiemos el siguiente elemento más pequeño en la siguiente posición de array
. También tenemos que incrementar i
si copiamos de lowHalf
, o incrementar j
si copiamos de highHalf
. Así que aquí están los arreglos antes y después de que el primer elemento se copie de regreso en array
:Atenuamos
highHalf[0]
para indicar que ya no contiene ningún valor que vamos a considerar. La parte no mezclada del arreglo highHalf
empieza en el índice j
, que ahora es 1. El valor en array[p]
ya no está atenuado porque le copiamos un valor "real".¿En dónde debe estar el siguiente valor que vamos a copiar de regreso en
array
? Es el primer elemento no tomado en lowHalf
(lowHalf[0]
) o el primer elemento no tomado de highHalf
(highHalf[1]
). Con una comparación, determinamos que lowHalf[0]
es más pequeño, así que lo copiamos a array[k]
e incrementamos k
e i
:A continuación, comparamos
lowHalf[1]
y highHalf[1]
, y determinamos que debemos copiar highHalf[1]
a array[k]
. Después incrementamos k
y j
:Seguimos adelante, siempre comparando
lowHalf[i]
y highHalf[j]
, copiando el más pequeño de los dos en array[k]
, e incrementando o i
o j
:Eventualmente, todo
lowHalf
o todo highHalf
se copia de regreso en array
. En este ejemplo, todo highHalf
se copia de regreso antes que los últimos elementos de lowHalf
. Terminamos por copiar los elementos restantes no tomados de lowHalf
o de highHalf
:Afirmamos que mezclar n elementos tarda un tiempo \Theta, left parenthesis, n, right parenthesis y, por lo tanto, el tiempo de ejecución de mezclar es lineal en el tamaño del subarreglo. Vamos a ver por qué esto es cierto. Vimos tres partes para mezclar:
- Copiar cada elemento en
array[p..r]
alowHalf
o ahighHalf
. - Siempre que haya elementos no tomados tanto en
lowHalf
como enhighHalf
, compara los primero dos elementos no tomados y copia el más pequeño de regreso enarray
. - Cuando cualquiera de lo dos,
lowHalf
ohighHalf
, tenga todos sus elementos copiados de regreso enarray
, copia cada elemento restante no tomado del otro arreglo temporal de regreso enarray
.
¿Cuántas líneas de código necesitamos para ejecutar cada uno de estos pasos? Es un número constante por elemento. Cada elemento se copia de
array
a lowHalf
o a highHalf
exactamente una vez en el paso 1. Cada comparación en el paso 2 toma un tiempo constante, ya que solo compara dos elementos, y cada elemento "gana" una comparación a lo más una vez. Cada elemento se copia de regreso en array
exactamente una vez en los pasos 2 y 3, combinados. Como ejecutamos cada línea de código un número constante de veces por elemento y suponemos que el subarreglo array[p..q]
contiene n elementos, el tiempo de ejecución para la mezcla es en efecto \Theta, left parenthesis, n, right parenthesis.En el siguiente desafío, vas a implementar esta operación de mezclado en tiempo lineal. Con los dos desafíos combinados, habrás implementado completamente el algoritmo de ordenamiento por mezcla.
Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.
¿Quieres unirte a la conversación?
- Que tal difícil es el ordenamiento de mezclas(3 votos)
- no tanto porque yo no sabia esas cosas(1 voto)
- Que Es Mezcla En Tiempo Lineal(2 votos)
- porque se le incluye a la funcion merge en la funcion array(1 voto)
- Puedes volver a redactar tu pregunta para ayudarte(1 voto)