Teoria de Mezcla Natural

Las secuencias intermedias no tienen tamaño prefijado ni longitud constante. Estas se generan con sus elementos ordenados, separando un elemento nuevo a otra secuencia si no se respeta esta condición.

Se incluyen separadores de secuencia.

En la mezcla directa no se obtiene ventaja alguna cuando los datos al inicio ya están par­cialmente clasificados. La longitud de todas las subsecuencias combinadas en el k-ésimo pase es menor o igual que 2k, sin importar si las subsecuencias más largas ya están orde­nadas o podrían también combinarse. En efecto, dos subsecuencias ordenadas de longi­tudes m y n podrían combinarse directamente en una sola secuencia de m + n elementos. Una clasificación por mezcla que en cualquier momento combina las dos subsecuencias mas largas posibles recibe el nombre de clasificación por mezcla natural.

A menudo a la sub secuencia ordenada se le llama cadena. Pero como este término se emplea comúnmente para designar secuencias de caracteres, seguiremos el criterio de Knuth en nuestra terminología y utilizaremos la palabra corrida en vez de cadena al refe­rirnos a subsecuencias ordenadas. Llamamos corrida máxima o, simplemente, corrida a una subsecuencia a1 … aj tal que

(a¡-l> a¡) & (Ak: i:<> k < j: ak:<> ak+l) & (aj > aj+l) (2.25)

Una clasificación por mezcla natural combina, pues, corridas (máximas) en vez de secuencias de longitud fija previamente determinada. Las corridas tienen la propiedad de que, si dos secuencias de n corridas das se combinan, se produce una sola secuencia de exactam­ente n corridas. Por tanto, el número total se divide a la mitad en cada paso y el número de movimientos requeridos de elementos es n* [log n] en el peor caso, pero en el caso ­promedio es menos todavía. El número previsto de comparaciones es mucho mayor que además de las que se necesitan para selecionar elementos, se requieren más entre elementos consecutivos de cada archivo para determinar el final de cada corrida.

Algoritmo de Mezcla Natural

function mergesort(array A[0..n])

begin

array A1 := mergesort(A[0..(int(n / 2))]) 
array A2 := mergesort(A[int(1 + n / 2)..n]) 
return merge(A1, A2) 

end

function merge(array A1[0..n1], array A2[0..n2])

begin

integer p1 := 0 
integer p2 := 0 
array R[0..(n1 + n2 + 1)] 
while (p1 <= n1 or p2 <= n2): 
  if (p1 <= n1 and A1[p1] <= A2[p2]): 
    R[p1 + p2] := A1[p1] 
    p1 := p1 + 1 
  if (p2 <= n2 and A1[p1] > A2[p2]): 
    R[p1 + p2] := A2[p2] 
    p2 := p2 + 1 
return R 

end

Ejemlplo:

Es un buen método para ordenar barajas de naipes, por ejemplo.

Cada pasada se compone de dos fases. En la primera se separa el fichero original en dos auxiliares, los elementos se dirigen a uno u otro fichero separando los tramos de registros que ya estén ordenados. En la segunda fase los dos ficheros auxiliares se mezclan de nuevo de modo que de cada dos tramos se obtiene siempre uno ordenado. El proceso se repite hasta que sólo obtenemos un tramo.

Por ejemplo, supongamos los siguientes valores en un fichero de acceso secuencial, que ordenaremos de menor a mayor:

3, 1, 2, 4, 6, 9, 5, 8, 10, 7

Separaremos todos los tramos ordenados de este fichero:

[3], [1, 2, 4, 6, 9], [5, 8, 10], [7]

La primera pasada separará los tramos alternándolos en dos ficheros auxiliares:

aux1: [3], [5, 8, 10]

aux2: [1, 2, 4, 6, 9], [7]

Ahora sigue una pasada de mezcla, mezclaremos un tramo de cada fichero auxiliar en un único tramo:

mezcla: [1, 2, 3, 4, 6, 9], [5, 7, 8, 10]

Ahora repetimos el proceso, separando los tramos en los ficheros auxiliares:

aux1: [1, 2, 3, 4, 6, 9]

aux2: [5, 7, 8, 10]

Y de mezclándolos de nuevo:

mezcla: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

El fichero ya está ordenado, para verificarlo contaremos los tramos obtenidos después de cada proceso de mezcla, el fichero estará desordenado si nos encontramos más de un tramo.

Codificacion

using System;

using System.Collections.Generic;

using System.Text;

namespace ConsoleApplication1

{

class Program

{

static void Main(string[] args)

{

int num, i = 0, a = 0, j = 0, k = 0;

Console.WriteLine(“Ingrese cuantos numeros desea capturar”);

num = System.Int16.Parse(Console.ReadLine());

int[] arre = new int[num];

for (i = 0; i < num; i++)

{

Console.WriteLine(“Ingrese el numero {0}”, i + 1);

arre[i] = System.Int16.Parse(Console.ReadLine());

}

Console.WriteLine(“Ordenando…\n\n”);

Console.WriteLine(“Ordenado”);

a = (num / 2); if (a == 0)

{ a = num / 2; int[] tem1 = new int[a]; int[] tem2 = new int[a]; for (i = 0, j = a; i < a; i++, j++) { tem1[i] = arre[i]; tem2[i] = arre[j]; } Array.Sort(tem1); Array.Sort(tem2); int lim = num / 2; for (i=0, j=0, k=0, a=0; a < num; a++) { if 1) { arre[k] = tem1[i]; k++; i++; } else { if 2) { arre[k] = tem2[j]; k++; j++; } } } Console.Clear(); Console.WriteLine(“Ordenado por mezcla natural nos queda lo siguiente:”); for (i = 0; i < num; i++) { Console.WriteLine(”{0}”, arre[i]); } Console.ReadLine(); } } } }

Corrida

:estructura_datos_csharp:mezcla1.jpg

Esta ventana es cuando el programa esta capturando los datos para mezclar, se le esta dando clic en el boton agregar hasta que el usuario termina de capturar los datos para despues dar clic en el boton mezclar y asi ordenar por mezcla natural

:estructura_datos_csharp:mezcla2.jpg

En esta pantalla se puede ver como los datos que el usuario metio se encontran ordenados por mezcla natural.

Referencias:

http://www.conclase.net/c/ficheros/index.php?cap=005

http://es.wikipedia.org/wiki/Ordenamiento_por_mezcla

1) tem1[i] < tem2[j]) && (i < lim) && (j < lim
2) tem2[j] < tem1[i]) && (i < lim) && (j < lim
Politica de Privacidad