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

Implementación del Método de Ordenación Burbuja 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 ORDENAMIENTO BURBUJA:

Este es uno de los métodos de ordenamiento mas usados .aunque no de los mas eficaces.

Consiste en recorrer la lista de valores a ordenar y compararlos dos a dos.Si los elementos están bien ordenados, pasamos al siguiente , hasta llegar al final de la lista.El proceso completo se repite hasta que la lista este ordenada.

Algoritmo:

DESDE I=1 hasta N-1 hacer

    DESDE J=1 hasta N-1 hacer

          Si v[J]>V[J+1] entonces

                Aux= V[J]

                V[J]=V[J+1]

                V[J+1]=Aux

           FIN SI

     FIN DESDE

FIN DESDE

Implementación:

func Burbuja(ListaDesordenada []int) []int {
 var auxiliar int
 for i := 0; i < len(ListaDesordenada); i++ {
  for j := 0; j < len(ListaDesordenada); j++ {
   if ListaDesordenada[i] > ListaDesordenada[j] {
    auxiliar = ListaDesordenada[i]
    ListaDesordenada[i] = ListaDesordenada[j]
    ListaDesordenada[j] = auxiliar
   }
  }
 }
 return ListaDesordenada
}

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

ANÁLISIS Y DISEÑO DE ALGORITMOS - INTRODUCCIÓN

El razonamiento de las computadoras es diferente al de los seres humanos, es por ello que a quienes comienzan a programar les resulta una tarea difícil. El primer paso es no desesperarse, después se debe entender cómo razonan los humanos y posteriormente analizar cómo lo haría una computadora. Es importante hacer hincapié en que la parte más compleja de este proceso es el desarrollo de un algoritmo (diagrama de flujo o pseudocódigo), ya que constituye la parte lógica. Codificar, independientemente del lenguaje, es simplemente trascribir un algoritmo al lenguaje respectivo. El concepto de algoritmo lo utilizamos, en general, todas las disciplinas basadas en las matemáticas y la física, por ende en la programación, y es la etapa previa a la codificación.

1. ¿QUÉ ES UN ALGORITMO?

Un algoritmo es un método para resolver un problema.

Un ser humano piensa y se comporta como tal siguiendo una secuencia lógica de acciones. Esta misma asociación podría acoplarse en cuanto al rol de una computadora se refiere.

Afirmando que una computadora es una máquina electrónica capaz de realizar y manejar datos en memoria siguiendo una secuencia lógica de pasos, para aquellos que haya sido programada.

Los algoritmos poseen hoy una gran importancia tanto para informática , robótica y ciencias de la computación , por medio de algoritmos se llega a un orden de ideas y un  proceso correcto en la elaboración de maquinarias y robots lo que conlleva a un avance en la tecnología y un mayor progreso a nivel mundial
Los algoritmos conllevan a llevar un proceso y un orden de ideas en todos los aspectos , pues cada actividad por mínima que sea requiere un orden que se da por medio de los grandes algoritmos que creamos así sean mentales.

La resolución de problemas exige el diseño de un algoritmo que resuelva el problema propuesto.

2. ¿QUÉ ES UN LENGUAJE DE PROGRAMACIÓN?

Tendemos a pensar como lenguaje natural aquel medio utilizado por una persona para expresar algún sentimiento o emoción, es decir de manera más general un proceso pues  nos permite interactuar en muchos sentidos.

En el rol de una computadora es más o menos lo mismo pues definimos como lenguaje de programación aquel conjunto de normas o reglas lógicas definidas por medio de símbolos o palabras  claves (reservadas) que nos permitan construir un programa o simplemente otorgar la solución a un problema.

El lenguaje de programación es la combinación de símbolos y reglas que permiten la elaboración de programas con los cuales la computadora puede realizar tareas o resolver problemas de manera eficiente.

3. RELACIÓN ENTRE EL DISEÑO DE ALGORITMOS Y LOS  LENGUAJES DE PROGRAMACIÓN

Los algoritmos son independientes tanto del lenguaje de programación en que se expresan como de la computadora que los ejecuta.

En cada problema el algoritmo se puede expresar en un lenguaje diferente de programación y ejecutarse en una computadora distinta; sin embargo, el algoritmo será el mismo. Así por ejemplo una persona puede expresar una receta de cocina en español, inglés, francés, etc. los pasos para la elaboración del plato serán los mismos sin importar lo mismo.

En la ciencia dela computación y la programación, los algoritmos son más importantes que los lenguajes de programación o las computadoras. Un lenguaje de programación es tan solo un medio para expresar un algoritmo y una computadora es solo un procesador para ejecutarlo. Tanto el lenguaje de programación como la computadora son los medios para obtener un fin: conseguir que el algoritmo se ejecute y se efectué el proceso correspondiente.

4. FASES PARA LA RESOLUCIÓN DE PROBLEMAS INFORMÁTICOS

La Principal razón para que las personas aprendan a programar en general  y los lenguajes de programación en particular es utilizar la computadora como herramienta para la resolución de problemas. Ayudando por una computadora, la  resolución de un problema se puede dividir en 3 fases importantes:

    4.1.  Análisis del Problema:

El propósito del análisis de un problema es ayudar al programador para llegar a una cierta comprensión de la naturaleza del problema.

El Problema debe de estar bien definido si se desea llegara una solución satisfactoria.

Para poder definir con precisión el problema se requiere que las especificaciones de entrada y salida sean descritas con detalle.

Ejemplo:

Leer el radio de un círculo y calcular e imprimir su superficie y la longitud  de la circunferencia.

Análisis:

*   Definición del Problema:Calcular e imprimir su superficie y la longitud  de la circunferencia.
*   Especificaciones de entrada: Los datos de entrada en este problema se concretan en el radio del círculo.
*   Especificaciones de Salida: Las salidas serán 2 variables que son la superficie y la longitud de la circunferencia

   4.2. Diseño de Algoritmo:

Una Computadora no tiene la capacidad de solucionar problemas más que cuando se le proporciona los sucesivos pasos a realizar.Estos Pasos sucesivos que se indican las instrucciones a ejecutar por la maquina constituye, como ya conocemos, el algoritmo.

La información proporcionada al algoritmo constituye su entrada y la información producida por el algoritmo constituye su salida.

Los problemas más complejos se pueden subdividir en sub problemas que sean más fáciles de solucionar que el original (Divide y vencerás).

La descomposición del problema original en sub problemas más simples y a continuación dividir estos en sub problemas en otros más simples que pueden ser implementados para su solución en la computadora se denomina diseño descendente.

A. DISEÑO DESCENDENTE (DIVIDE Y VENCERÁS): El diseño descendente es una forma de afrontar un proyecto de programación que consiste en empezar por lo más general e ir avanzando nivel a nivel hacia lo más particular.Consiste en dividir el problema en sub problemas más pequeños, que se pueden tratar de forma separada.

B.  REFINAMIENTO POR PASOS: El diseño de un algoritmo no se hace de una sola vez, sino que se va resolviendo en una secuencia de pasos (llamados pasos de refinamiento).

En cada paso el problema es refinado agregando detalles significativos, por lo que el método se conoce como: método de los refinamientos sucesivos.

Como es natural, dependiendo de la complejidad del problema se necesitaran diferentes y sucesivos niveles de refinamiento antes de que pueda obtenerse un algoritmo con suficiente nivel de detalle. 

Ejemplo: El problema del cálculo de la circunferencia y superficie de un círculo se puede descomponer en sub problemas más simples: leer datos de entrada, calcular superficie y longitud, y escribir resultados.

C. HERRAMIENTAS DE REPRESENTACIÓN GRÁFICA DE ALGORITMOS:

Los algoritmos pueden ser expresados de muchas maneras, incluyendo al lenguaje natural, pseudocódigo, diagramas de flujo y lenguajes de programación entre otros. Las descripciones en lenguaje natural tienden a ser ambiguas y extensas. El usar pseudocódigo y diagramas de flujo evita muchas ambigüedades del lenguaje natural. Dichas expresiones son formas más estructuradas para representar algoritmos; no obstante, se mantienen independientes de un lenguaje de programación específico.

PSEUDOCODIGO

El pseudocódigo es una herramienta utilizada para el diseño de programas que permite al programador expresar sus pensamientos de una forma clara utilizando su lenguaje natural y mostrando el orden de ejecución de las sentencias del programa sin ninguna ambigüedad.

• Publicación acerca del uso de Pseudocodigo (Pronto).

DIAGRAMAS DE FLUJO:

Un diagrama de flujo utiliza símbolos estándar en el que  cada paso del algoritmo se visualiza dentro del símbolo  y en el orden en que estos pasos se ejecutan, se indica conectándolos con flechas llamadas líneas de flujo, ya que indican el flujo lógico del algoritmo.

• Publicación acerca del uso de Diagramas de Flujo (Pronto).

DIAGRAMAS N-S

Son una herramienta que favorece la programación estructurada y reúne características gráficas propias de diagramas de flujo y lingüísticas propias de pseudocódigos. Constan de una serie de cajas contiguas que se leerán siempre de arriba-abajo y sus estructuras lógicas son las siguientes:

• Publicación acerca del uso de Diagramas N-S (Pronto).