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
}

• Tweet
• Share
• Share
• Share
• Share