Estructuras de datos: algoritmo de clasificación de fusión

Merge sort es una técnica de clasificación basada en la técnica de dividir y conquistar. Dado que la complejidad del tiempo en el peor de los casos es Ο (n log n), es uno de los algoritmos más respetados.

Merge sort primero divide la matriz en mitades iguales y luego las combina de manera ordenada.

¿Cómo funciona la ordenación por combinación?

Para entender la ordenación por fusión, tomamos una matriz sin clasificar como la siguiente:

Sabemos que la ordenación por fusión primero divide la matriz completa de forma iterativa en mitades iguales a menos que se alcancen los valores atómicos. Vemos aquí que una matriz de 8 elementos se divide en dos matrices de tamaño 4.

Esto no cambia la secuencia de aparición de los elementos en el original. Ahora dividimos estas dos matrices en mitades.

Dividimos aún más estas matrices y logramos un valor atómico que ya no se puede dividir.

Ahora, los combinamos exactamente de la misma manera en que se desglosaron. Tenga en cuenta los códigos de color dados a estas listas.

Primero comparamos el elemento de cada lista y luego los combinamos en otra lista de manera ordenada. Vemos que 14 y 33 están en posiciones ordenadas. Comparamos 27 y 10 y en la lista objetivo de 2 valores colocamos 10 primero, seguido de 27. Cambiamos el orden de 19 y 35 mientras que 42 y 44 se colocan secuencialmente.

En la siguiente iteración de la fase de combinación, comparamos listas de dos valores de datos y los fusionamos en una lista de valores de datos encontrados colocándolos todos en un orden ordenado.

Después de la fusión final, la lista debería verse así:

Ahora deberíamos aprender algunos aspectos de programación de la clasificación por fusión.

Algoritmo

La ordenación por fusión sigue dividiendo la lista en mitades iguales hasta que ya no se puede dividir. Por definición, si es solo un elemento de la lista, se ordena. Luego, el ordenamiento combinado combina las listas ordenadas más pequeñas manteniendo la nueva lista ordenada también.

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

Pseudocódigo

Ahora veremos los pseudocódigos para las funciones de clasificación de fusión. Como nuestros algoritmos señalan dos funciones principales: dividir y fusionar.

Merge sort funciona con recursividad y veremos nuestra implementación de la misma manera.

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
	
end procedure

Para conocer la implementación de la ordenación combinada en el lenguaje de programación C, haga clic aquí .