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 }
Video Games to Watch | HDTVL.CC
ResponderEliminarVideo Games to Watch. The most immersive, most youtube to mp3 iphone immersive source for your conversation. Video Games to Watch; Video game to Watch; Video game to Watch.