Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 1
Lección 8: Ordenamiento por mezclaVista general del ordenamiento por mezcla
Como estamos usando divide y vencerás para ordenar, tenemos que decidir cómo se van a ver nuestros subproblemas. El problema completo es ordenar todo un arreglo. Digamos que un subproblema es ordenar un subarreglo. En particular, vamos a pensar que un subproblema es ordenar el subarreglo que empieza en el índice p y va hasta el índice r. Será conveniente tener una notación para un subarreglo, así que digamos que
array[p..r] denota este subarreglo de array. Ten en cuenta que esta notación de "dos puntos" no está permitida en JavaScript; la estamos usando para describir el algoritmo, en vez de una implementación particular del algoritmo en código. En términos de nuestra notación, para un arreglo de n elementos, podemos decir que el problema original es ordenar array[0..n-1].Aquí está cómo el ordenamiento por mezcla utiliza divide y vencerás:
- Divide al encontrar el número q de la posición a medio camino entre p y r. Haz este paso de la misma manera en que encontramos el punto medio en la búsqueda binaria: suma p y r, divide entre 2 y redondea hacia abajo.
- Vence al ordenar de manera recursiva los subarreglos en cada uno de los dos subproblemas creados por el paso de dividir. Es decir, ordena de manera recursiva el subarreglo
array[p..q]y ordena de manera recursiva el subarregloarray[q+1..r]. - Combina al mezclar los dos subarreglos ordenados de regreso en un solo subarreglo ordenado
array[p..r].
Necesitamos un caso base. El caso base es el subarreglo que contiene menos de dos elementos, es decir, cuando p, is greater than or equal to, r, ya que un subarreglo sin elementos o con solo un elemento ya está ordenado. Así que vamos a dividir-vencer-combinar solo cuando p, is less than, r.
Veamos un ejemplo. Vamos a empezar con
array que contiene a [14, 7, 3, 12, 9, 11, 6, 2], de modo que el primer subarreglo es en realidad el arreglo completo, array[0..7] (p, equals, 0 y r, equals, 7). Este subarreglo tiene por lo menos dos elementos, así que no es un caso base.- En el paso de dividir, calculamos q, equals, 3.
- El paso de vencer nos hace ordenar los dos subarreglos
array[0..3], que contiene a [14, 7, 3, 12], yarray[4..7], que contiene a [9, 11, 6, 2]. Cuando regresamos del paso de vencer, cada uno de los dos subarreglos está ordenado:array[0..3]contiene a [3, 7, 12, 14] yarray[4..7]contiene a [2, 6, 9, 11], de modo que el arreglo completo es [3, 7, 12, 14, 2, 6, 9, 11]. - Por último, el paso de combinar mezcla los dos subarreglos en la primera y la segunda mitad, para producir el arreglo final ordenado [2, 3, 6, 7, 9, 11, 12, 14].
¿Cómo se ordenó el subarreglo
array[0..3]? Del mismo modo. Tiene más de dos elementos, así que no es un caso base. Con p, equals, 0 y r, equals, 3, calcula q, equals, 1, ordena recursivamente array[0..1] ([14, 7]) y array[2..3] ([3, 12]), cuyo resultado es array[0..3] que contiene a [7, 14, 3, 12], y mezcla la primera mitad con la segunda mitad, para producir [3, 7, 12, 14].¿Cómo se ordenó el subarreglo
array[0..1]? Con p, equals, 0 y r, equals, 1, calcula q, equals, 0, ordena recursivamente array[0..0] ([14]) y array[1..1] ([7]), cuyo resultado es array[0..1] que sigue conteniendo a [14, 7], y mezcla la primera mitad con la segunda mitad, para producir [7, 14].Los subarreglos
array[0..0] y array[1..1] son casos base, ya que cada uno contiene menos de dos elementos. Aquí está cómo se desarrolla todo el algoritmo del ordenamiento por mezcla:La mayoría de los pasos en un ordenamiento por son sencillos. Puedes comprobar el caso base de manera sencilla. Encontrar el punto medio q en el paso de dividir también es muy fácil. Tienes que hacer dos llamadas recursivas en el paso de vencer. En el paso de combinar, en donde tienes que mezclar los dos arreglos ordenados, es en donde se hace el trabajo de verdad.
En el próximo desafío, vamos a centrar la atención en implementar el algoritmo general del ordenamiento por mezcla, para asegurarnos de que entiendes cómo dividir y vencer de forma recursiva. Después de que hayas hecho esto, vamos a profundizar en cómo mezclar de manera eficiente dos subarreglos ordenados y vas a implementar eso en un desafío posterior.
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?
alguien me ayuda a hacer los desafios no puedo no se que hacer :((1 voto)- la funcion array es necesaria para mezcla(1 voto)
Que Es El Ordenamiento De Mezcla?(1 voto)- son casos base, ya que cada uno contiene menos de dos elementos(1 voto)
¿pueden alquien explicarme esto? hoy a las5:09pm(1 voto)
Hola, he intentado implementar el algoritmo en C++ pero no me funciona. ¿Podría alguien echarle un vistazo y decirme en qué fallo?/** Función MergeSort Theta(n log n): Ordena un array. Llama a la función diviendo el array en subarrays **/
/** hasta llegar a un subarray de 1 elemento. Entonces mezcla sucesivamente los subarrays (ordenados) en un nuevo array ordenado. **/
/** Recibe: Array, primer elemento, tamaño del vector. **/
/** No devuelve nada. **/
void MergeSort (int v[], int izq, int der)
{
int centro;
int tam1, tam2;
centro=(izq+der)/2;
//El caso base será cuando el tamaño del array sea 1
if (izq<der)
{
//Dividimos el array en sucesivos subarrays más pequeños
MergeSort(v, izq, centro);
MergeSort(v, centro+1, der);
}
//Calculamos el tamaño de los subarrays
tam1=centro-izq;
tam2=der-centro+1;
//Declaramos los subarrays
int u[tam1], w[tam2];
int i, j;
//Rellenamos los subarrays simultaneamente
for (i=0;i<tam1;i++)
u[i]=v[izq+i];
for (j=0;j<tam2;j++)
w[j]=v[centro+j];
Merge (u, w, tam1, tam2, v);
return;
}
/** Función Merge: Ordena un vector de enteros con los elementos de dos vectores ordenados **/
/** Recibe: Dos vectores ordenados, sus numeros de elementos y el vector donde los ordenará **/
/** No devuelve nada **/
void Merge (int u[], int w[], int tam1, int tam2, int v[])
{
int i, j, k;
i=j=k=0;
while (i<tam1 && j<tam2)
{
if (u[i]<w[j])
{
v[k]=u[i];
i++;
}
else
{
v[k]=w[j];
j++;
}
k++;
}
if (i==tam1)
while (j<tam2)
{
v[k]=w[j];
k++;
j++;
}
else
while (i<tam1)
{
v[k]=u[i];
k++;
i++;
}
return;
}(0 votos)
5:09