jueves, 20 de septiembre de 2018

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
}

banner
Previous Post
Next Post

Hola, me llamo Andrés.Soy egresado de la carrera de Ingeniería Informática en la Universidad Nacional de Trujillo (Perú).Me considero autodidacta de corazón ,amante del mundo de la programación, software libre y hacking ético

0 comentarios: