Implementación del método de ordenación MergeSort en Golang

La tarea de la programación esta ligada al objetivo de obtener algoritmos que resuelvan un problema con la mayor eficiencia posible; de hecho es sorprendente comprobar las múltiples formas como podemos resolver un mismo problema y las ventajas que conseguimos , en términos de eficiencia , al buscar soluciones alternativas a las ya conocidas o consideradas como evidentes.

Para comparar y analizar la eficiencia de los algoritmos , estos los consideramos escritos en un lenguaje de programación de alto nivel , pero aun empleando la misma representación , establecer una medida precisa de la eficiencia de un algoritmo no es fácil.En efecto , fijémonos en que una definición de eficiencia podría ser el numero de instrucciones que tiene el programa ; sin embargo esto no se correspondería , con el concepto intuitivo que tenemos de eficiencia(según el cual,el algoritmo mas eficiente seria aquel que tardase menos tiempo en resolver el problema sobre una misma maquina), dado que todas las instrucciones no utilizan el mismo tiempo de procesador aun realizando la misma función.

MÉTODO DE ORDENACIÓN MERGESORT:

Este algoritmo consiste básicamente en dividir en partes iguales la lista de números y luego mezclarlos comparándolos, dejándolos ordenados.

Si se piensa en este algoritmo recursivamente, podemos imaginar que dividirá la lista hasta tener un elemento en cada lista, luego lo compara con el que está a su lado y según corresponda, lo sitúa donde corresponde.

En la siguiente figura podemos ver cómo funciona:

Implementación

package main

import "fmt"

//METODO DE ORDENACION: MERGESORT
func main() {
 var ListaDesordenada = []int{15, 3, 8, 6, 18, 1}
 ListaOrdenada := mergeSort(ListaDesordenada, 0, len(ListaDesordenada)-1)
 fmt.Println(ListaDesordenada)
}
func mergeSort(ListaDesordenada []int, iMin int, iMax int) []int {
 // Caso Base
 if iMin >= iMax {
  return ListaDesordenada
 }
 // Cortamos para aplicar mergeSort recursivamente
 k := (iMin + iMax) / 2
 mergeSort(ListaDesordenada, iMin, k)
 mergeSort(ListaDesordenada, k+1, iMax)
 // Utilizamos un arreglo temporal
 l := iMax - iMin + 1
 var temp = []int{}
 for i := 0; i < l; i++ {
  temp[i] = ListaDesordenada[iMin+i]
 }
 // Mezclamos
 i1 := 0
 i2 := k - iMin + 1
 for i := 0; i < l; i++ {
  if i2 <= iMax-iMin {
   if i1 <= k-iMin {
    if temp[i1] > temp[i2] {
     ListaDesordenada[i+iMin] = temp[i2+1]
    } else {
     ListaDesordenada[i+iMin] = temp[i1+1]
    }
   } else {
    ListaDesordenada[i+iMin] = temp[i2+1]
   }
  } else {
   ListaDesordenada[i+iMin] = temp[i1+1]
  }
 }
 return ListaDesordenada
}

Espero que les sea de utilidad y hasta la próxima

• Tweet
• Share
• Share
• Share
• Share