Mostrando entradas con la etiqueta mezcla directa. Mostrar todas las entradas
Mostrando entradas con la etiqueta mezcla directa. Mostrar todas las entradas

viernes, 3 de enero de 2014

Ordenación Externa: Mezcla Directa

Mezcla Directa.

El método de ordenación por mezcla directa es probablemente el más utilizado por su fácil comprensión.

La idea central de este algoritmo consiste en la realización sucesiva de una partición y una fusión que produce secuencias ordenadas de longitud cada vez mayor. En la primera pasada la partición es de longitud 1, y la fusión o mezcla produce secuencias ordenadas de longitud 2. En la segunda pasada la partición es de longitud 2, y la fusión o mezcla produce secuencias ordenadas de longitud 4. Este proceso se repite hasta que la longitud de la secuencia de la secuencia para la partición sea mayor o igual que el número de elementos del archivo original.

Ejemplo:

Supóngase que se desea ordenar las claves del archivo F. para realizar tal actividad se utilizan dos archivos auxiliares a los que se les denominará. F1 y F2.

F: 09 75 14 68 29 17 31 25 04 05 13 18 72 46 61.

Primera pasada:

Partición en secuencias de longitud 1.

F1: 09’ 14’ 29’ 31’ 04’ 13’ 72’ 61’

F2: 75’ 68’ 17’ 25’ 05’ 18’ 46’

Fusión en secuencias de longitud dos:

F: 09 75’ 14 68’ 17 29’ 25 31’ 04 05’ 13 18’ 46 72’ 61’

Segunda pasada:

Partición de secuencia de longitud 2

F1: 09 75’ 17 29’ 04 05’ 46 72’

F2: 14 68’ 25 31’ 13 18’ 61’

Fusión en secuencias de longitud 4.

F: 09 14 68 75’ 17 25 29 31’ 04 05 13 18’ 46 61 72’

Tercera pasada.

Partición en secuencia de longitud 4.

F1: 09 14 68 75’ 04 05 13 18’

F2: 17 25 29 31’ 46 61 72’

Fusión en secuencias de longitud 8

F: 09 14 17 25 29 31 68 75’ 04 05 13 18 46 61 72’

Cuarta pasada.

Partición en secuencia de longitud 8

F1: 09 14 17 25 29 31 68 75’

F2: 04 05 13 18 46 61 72’

Fusión en secuencias de longitud 16

F: 04 05 09 13 14 17 18 25 29 31 46 61 68 72 75