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

MÉTODO DE ORDENACIÓN HEAPSORT

Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteracciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él. El algoritmo, después de cada extracción, re coloca en el nodo raíz o cima, la última hoja por la derecha del último nivel. Lo cual destruye la propiedad heap del árbol. Pero, a continuación realiza un proceso de "descenso" del número insertado de forma que se elige a cada movimiento el mayor de sus dos hijos, con el que se intercambia. Este intercambio, realizado sucesivamente "hunde" el nodo en el árbol restaurando la propiedad montículo del árbol y dejando paso a la siguiente extracción del nodo raíz.

Implementación

package main

import "fmt"

func main() {
 var ListaDesordenada = []int{15, 3, 8, 6, 18, 1}
 ListaOrdenada := heapSort(ListaDesordenada)
 fmt.Println(ListaOrdenada)
}

// METODO DE ORDENACION: HEAP SORT
func heapSort(ListaDesordenada []int) []int {
 var ListaOrdenada = []int{}
 N := len(ListaDesordenada)
 for nodo := N / 2; nodo >= 0; nodo-- {
  ListaOrdenada = doHeapSort(ListaDesordenada, nodo, N-1)
 }
 for nodo := N - 1; nodo >= 0; nodo-- {
  tmp := ListaDesordenada[0]
  ListaDesordenada[0] = ListaDesordenada[nodo]
  ListaDesordenada[nodo] = tmp
  ListaOrdenada = doHeapSort(ListaDesordenada, 0, nodo-1)
 }
 return ListaOrdenada
}
func doHeapSort(ListaDesordenada []int, nodo int, fin int) []int {
 izq := 2*nodo + 1
 der := izq + 1
 var may int
 if izq > fin {
  return ListaDesordenada
 }
 if der > fin {
  may = izq
 } else {
  if ListaDesordenada[izq] > ListaDesordenada[der] {
   may = izq
  } else {
   may = der
  }
 }
 if ListaDesordenada[nodo] < ListaDesordenada[may] {
  tmp := ListaDesordenada[nodo]
  ListaDesordenada[nodo] = ListaDesordenada[may]
  ListaDesordenada[may] = tmp
  doHeapSort(ListaDesordenada, may, fin)
 }
 return ListaDesordenada
}

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

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

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

En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación  o reordenamiento de la entrada que satisfaga la relación de orden dada. Los ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos.

MÉTODO DE ORDENACIÓN QUICKSORT:

Sin duda, este algoritmo es uno de los más eficientes. Este método es el más rápido gracias a sus llamadas recursivas, basándose en la teoría de divide y vencerás.

Lo que hace este algoritmo es dividir recursivamente el vector en partes iguales, indicando un elemento de inicio, fin y un pivote (o comodín) que nos permitirá segmentar nuestra lista. Una vez dividida, lo que hace, es dejar todos los mayores que el pivote a su derecha y todos los menores a su izquierda Al finalizar el algoritmo, nuestros elementos están ordenados.

Por ejemplo, si tenemos 3 5 4 8 básicamente lo que hace el algoritmo es dividir la lista de 4 elementos en partes iguales, por un lado 3, por otro lado 4 8 y como comodín o pivote el 5. Luego pregunta, 3 es mayor o menor que el comodín? Es menor, entonces lo deja al lado izquierda Y como se acabaron los elementos de ese lado, vamos al otro lado. 4 Es mayor o menor que el pivote? Menor, entonces lo tira a su izquierda. Luego pregunta por el 8, al ser mayor lo deja donde está, quedando algo así: 3 4 5 8.

En esta figura se ilustra de mejor manera un vector con más elementos, usando como pivote el primer elemento:

Algoritmo

// Inicialización de variables
    elem_div = lista[sup];
    i = inf - 1;
    j = sup;
    cont = 1;
    
    // Verificamos que no se crucen los límites
    if (inf >= sup)
          retornar;
    
    //  Clasificamos la sublista
    while (cont)
          while (lista[++i] < elem_div);
          while (lista[--j] > elem_div);
         if (i < j)
              temp = lista[i];
              lista[i] = lista[j];
              lista[j] = temp;
         else
              cont = 0;
   
   // Copiamos el elemento de división
   // en su posición final
    temp = lista[i];
    lista[i] = lista[sup];
    lista[sup] = temp;
   
   // Aplicamos el procedimiento
   // recursivamente a cada sublista
    OrdRap (lista, inf, i - 1);
    OrdRap (lista, i + 1, sup);

Implementación:

package main

import "fmt"

func main() {
 var ListaDesordenada = []int{15, 3, 8, 6, 18, 1}
 var N int = len(ListaDesordenada)
 ListaOrdenada := quicksort(ListaDesordenada, 0, N-1)
 fmt.Println(ListaOrdenada)
}

func quicksort(ListaDesordenada []int, izq int, der int) []int {
 pivote := ListaDesordenada[izq] // tomamos primer elemento como pivote
 i := izq                        // i realiza la búsqueda de izquierda a derecha
 j := der                        // j realiza la búsqueda de derecha a izquierda
 var aux int

 for i < j { // mientras no se crucen las búsquedas
  for ListaDesordenada[i] <= pivote && i < j {
   i++
  } // busca elemento mayor que pivote
  for ListaDesordenada[j] > pivote {
   j--
  } // busca elemento menor que pivote
  if i < j { // si no se han cruzado
   aux = ListaDesordenada[i] // los intercambia
   ListaDesordenada[i] = ListaDesordenada[j]
   ListaDesordenada[j] = aux
  }
 }
 ListaDesordenada[izq] = ListaDesordenada[j] // se coloca el pivote en su lugar de forma que tendremos
 ListaDesordenada[j] = pivote                // los menores a su izquierda y los mayores a su derecha
 if izq < j-1 {
  quicksort(ListaDesordenada, izq, j-1) // ordenamos subarray izquierdo
 }

 if j+1 < der {
  quicksort(ListaDesordenada, j+1, der) // ordenamos subarray derecho
 }
 return ListaDesordenada
}

Implementación del Método de ordenación Inserción en Golang

En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación  o reordenamiento de la entrada que satisfaga la relación de orden dada. Los ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos.

MÉTODO DE ORDENACIÓN INSERCIÓN:

La idea de este algoritmo de ordenación consiste en ir insertando un elemento de la lista o un arreglo en la parte ordenada de la misma, asumiendo que el primer elemento es la parte ordenada, el algoritmo ira comparando un elemento de la parte desordenada de la lista con los elementos de la parte ordenada, insertando el elemento en la posición correcta dentro de la parte ordenada, y así sucesivamente hasta obtener la lista ordenada. Para explicarlo mejor nos basaremos en el siguiente enunciado:

“Para cada elemento de la lista después del primero, comparar los elementos con los anteriores desplazando una posición a la derecha a todos los elementos anteriores que cumplan con la comparación y luego colocar el elemento en la posición del último elemento anterior desplazado.”

Algoritmo:

for (i=1; i<TAM; i++)
      aux = array[i];
      j = i - 1;
      while ( (array[j] > aux) && (j >= 0) )
          array[j+1] = array[j];
           j--;
      array[j+1] = aux;



Implementacion:

func Insercion(ListaDesordenada []int) []int {
 var auxiliar int
 for i := 1; i < len(ListaDesordenada); i++ {
  auxiliar = ListaDesordenada[i]
  for j := i - 1; j >= 0 && ListaDesordenada[j] > auxiliar; j-- {
   ListaDesordenada[j+1] = ListaDesordenada[j]
   ListaDesordenada[j] = auxiliar
  }
 }
 return ListaDesordenada
}

Espero les sirva y hasta la próxima oportunidad