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
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 array[0..n-1].Aquí está cómo el ordenamiento por mezcla utiliza divide y vencerás:
- Divide al encontrar el número
- 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
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] (- En el paso de dividir, calculamos
- 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 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 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
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 :((2 votos)- 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