MEZCLA NATURAL INTERNA ESTRUCTURA DATOS C#

Se incluyen separadores de secuencia. 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. Las secuencias intermedias

 

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 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 
MEZCLA NATURAL INTERNA ESTRUCTURA DATOS C#

MÁS INFORMACIÓN

El contenido original se encuentra en https://programacionfacil.com/estructura_datos_csharp/mezcla_natural_interna/
Todos los derechos reservados para el autor del contenido original (en el enlace de la linea superior)
Si crees que alguno de los contenidos (texto, imagenes o multimedia) en esta página infringe tus derechos relativos a propiedad intelectual, marcas registradas o cualquier otro de tus derechos, por favor ponte en contacto con nosotros en el mail [email protected] y retiraremos este contenido inmediatamente

Top 20