QuickSort - Historial de revisiones

Carlos idict: Texto reemplazado: «
» por «»

2019-09-01T12:15:41Z

Texto reemplazado: «<div align="justify">» por «»

Yalexy idict: /* Descripción del algoritmo */

2014-01-09T13:47:53Z

‎Descripción del algoritmo

Astroboy: /* Descripción del algoritmo */

2012-02-22T04:28:48Z

‎Descripción del algoritmo

Astroboy en 04:28 22 feb 2012

2012-02-22T04:28:12Z

Astroboy en 04:26 22 feb 2012

2012-02-22T04:26:53Z

Mostrar los cambios

Astroboy: Ordenamiento por Quicksort trasladada a QuickSort

2012-02-22T04:04:05Z

Ordenamiento por Quicksort trasladada a QuickSort

Manuel jc.manzanillo1 en 23:39 29 jul 2011

2011-07-29T23:39:20Z

Rolando01015jc en 13:09 5 abr 2011

2011-04-05T13:09:52Z

Mostrar los cambios

Rolando01015jc en 13:01 5 abr 2011

2011-04-05T13:01:56Z

Mostrar los cambios

Rolando01015jc: Página creada con '{{Definición |nombre=Ordenamiento por Quicksort |imagen=Quicksort.gif |tamaño= |concepto= }} '''El ordenamiento rápido,''' '''quicksort '''en inglés: Es un [[...'

2011-04-05T12:59:20Z

Página creada con '{{Definición |nombre=Ordenamiento por Quicksort |imagen=Quicksort.gif |tamaño= |concepto= }} '''El ordenamiento rápido,''' '''quicksort '''en inglés: Es un [[...'

Página nueva

{{Definición
|nombre=Ordenamiento por Quicksort
|imagen=Quicksort.gif
|tamaño=
|concepto=
}}

'''El ordenamiento rápido,''' '''[[quicksort|quicksort]] '''en inglés: Es un [[algoritmo|algoritmo]] basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

== Descripción del algoritmo ==

El algoritmo consta de los siguientes pasos:

#Elegir un elemento de la lista de elementos a ordenar, al que llamaremos [[pivote|pivote]].
#Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la [[implementación|implementación]] deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
#La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
#Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

== Eficiencia del algoritmo ==

La [[eficiencia del algoritmo|eficiencia del algoritmo]] depende de la posición en la que termine el pivote elegido. En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de [[complejidad del algoritmo|complejidad del algoritmo]] es O(n•log n). En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente. En el caso promedio, el orden es O(n•log n). Y no es extraño, pues, que la mayoría de [[optimizaciones|optimizaciones]] que se aplican al algoritmo se centren en la elección del pivote.

== Demostración ==

Suponiendo que el número total de elementos a ordenar es potencia de dos, es decir, n = 2k. De aquí podemos ver que k = log2(n), donde k es el número de divisiones que realizará el algoritmo.

En la primera fase del algoritmo habrán n comparaciones, en la segunda fase el algoritmo creará dos sublistas aproximadamente de tamaño n/2. El número total de comparaciones de estas dos sublistas es: 2(n/2) = n. En la tercera fase el algoritmo procesará 4 sublistas más, por tanto el número total de comparaciones en esta fase es 4(n/4) = n.

En conclusión, el número total de comparaciones que hace el algoritmo es:

n + n + n + ..... + n = kn, donde k = log2(n), por tanto el tiempo de ejecución del algoritmo en el mejor caso es O(n.log2n)

== Optimización del algoritmo ==

Cabe destacar que de usarse en su versión recursiva las siguientes optimizaciones y sus desventajas no se ven vistas en el tiempo de ejecución del mismo manteniéndose, así el tiempo de ejecución planteado en un principio.

== Técnicas de elección del pivote ==

El algoritmo básico del método Quicksort consiste en tomar cualquier elemento de la lista al cual denominaremos como pivote, dependiendo de la partición en que se elija, el algoritmo será más o menos eficiente. Tomar un elemento cualquiera como pivote tiene la ventaja de no requerir ningún cálculo adicional, lo cual lo hace bastante rápido. Sin embargo, esta elección «a ciegas» siempre provoca que el algoritmo tenga un orden de O(n²) para ciertas permutaciones de los elementos en la lista. Otra opción puede ser recorrer la lista para saber de antemano qué elemento ocupará la posición central de la lista, para elegirlo como pivote. Esto puede hacerse en O(n) y asegura que hasta en el peor de los casos, el algoritmo sea O(n•log n). No obstante, el cálculo adicional rebaja bastante la eficiencia del algoritmo en el caso promedio. La opción a medio camino es tomar tres elementos de la lista - por ejemplo, el primero, el segundo, y el último - y compararlos, eligiendo el valor del medio como pivote.

== Técnicas de reposicionamiento ==

Una idea preliminar para ubicar el pivote en su posición final sería contar la cantidad de elementos menores que él, y colocarlo un lugar más arriba, moviendo luego todos esos elementos menores que él a su izquierda, para que pueda aplicarse la [[recursividad|recursividad]].

Existe, no obstante, un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos índice izquierdo, y j, al que llamaremos índice derecho. El algoritmo es el siguiente:

Recorrer la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la derecha con j (desde el último elemento). Cuando lista[i] sea mayor que el pivote y lista[j] sea menor, se intercambian los elementos en esas posiciones.

Repetir esto hasta que se crucen los índices. El punto en que se cruzan los índices es la posición adecuada para colocar el pivote, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados).

== Parámetros:  ==

#Se debe llamar a la función Quicksort desde donde quiera ejecutarse
#Ésta llamará a colocar pivote para encontrar el valor del mismo
#Se ejecutará el algoritmo Quicksort de forma recursiva a ambos lados del pivote

 int colocar(int *v, int b, int t) { int i; int pivote, valor_pivote; int temp; pivote = b; valor_pivote = v[pivote]; for (i=b+1; i<=t; i++){ if (v[i] < valor_pivote){ pivote++; temp=v[i]; v[i]=v[pivote]; v[pivote]=temp; } } temp=v[b]; v[b]=v[pivote]; v[pivote]=temp; return pivote; } void Quicksort(int* v, int b, int t) { int pivote; if(b < t){ pivote=colocar(v, b, t); Quicksort(v, b, pivote-1); Quicksort(v, pivote+1, t); } }

Nota: Los tres parámetros de la llamada inicial a Quicksort serán array[0], 0, numero_elementos -1, es decir, si es un array de 6 elementos array[0], 0, 5

== Implementación del Pseudocódigo ==

function quicksort(array) var list, less, greater if length(array) ≤ 1 return array seleccionar y eliminar un valor pivote pivot en el array for each x in array if x < pivot then añadir x a less else añadir x a greater return concadenar(quicksort(less), pivot, quicksort(greater))

== Ejemplo ==

En el siguiente ejemplo se marcan el pivote y los índices i y j con las letras p, i y j respectivamente.

Comenzamos con la lista completa. El elemento pivote será el 4: 5 - 3 - 7 - 6 - 2 - 1 - 4 p

 Comparamos con el 5 por la izquierda y el 1 por la derecha. 5 - 3 - 7 - 6 - 2 - 1 - 4 i j p

 5 es mayor que 4 y 1 es menor. Intercambiamos: 1 - 3 - 7 - 6 - 2 - 5 - 4 i j p

 Avanzamos por la izquierda y la derecha: 1 - 3 - 7 - 6 - 2 - 5 - 4 i j p

 3 es menor que 4: avanzamos por la izquierda. 2 es menor que 4: nos mantenemos ahí. 1 - 3 - 7 - 6 - 2 - 5 - 4 i j p

 7 es mayor que 4 y 2 es menor: intercambiamos. 1 - 3 - 2 - 6 - 7 - 5 - 4 i j p

 Avanzamos por ambos lados: 1 - 3 - 2 - 6 - 7 - 5 - 4 iyj p

 En este momento termina el ciclo principal, porque los índices se cruzaron. Ahora intercambiamos lista[i] con lista[sup] (pasos 16-18): 1 - 3 - 2 - 4 - 7 - 5 - 6 p

 Aplicamos recursivamente a la sublista de la izquierda (índices 0 - 2). Tenemos lo siguiente: 1 - 3 - 2

 1 es menor que 2: avanzamos por la izquierda. 3 es mayor: avanzamos por la derecha. Como se intercambiaron los índices termina el ciclo. Se intercambia lista[i] con lista[sup]: 1 - 2 - 3

 El mismo procedimiento se aplicará a la otra sublista. Al finalizar y unir todas las sublistas queda la lista inicial ordenada en forma ascendente. 1 - 2 - 3 - 4 - 5 - 6 - 7

== ==

== Referencias ==

*[[Quick Sort|Quick Sort]] 
*[[Ordenamiento rápido, Implementación y descripción|Ordenamiento rápido, Implementación y descripción]]
*[[QuickSort C Code|QuickSort C Code]]
*[[Wikipedia|Wikipedia]]

 

[[Category:Algoritmos]]

@@ Línea 14: / Línea 14: @@
 #Elegir un elemento de la lista de elementos a ordenar, al que llamaremos [[Pivote|pivote]].
-#Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la [[Implementación|implementación]] deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
+#Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
 #La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
 #Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

@@ Línea 14: / Línea 14: @@
 #Elegir un elemento de la lista de elementos a ordenar, al que llamaremos [[Pivote|pivote]].
 #Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la [[Implementación|implementación]] deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
 #La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
 #Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

@@ Línea 1: / Línea 1: @@
 {{Definición
 |nombre=Ordenamiento por Quicksort
@@ Línea 6: / Línea 7: @@
 }}
-'''QuickSort''' (en inglés, ordenamiento rápido): Es un [[Algoritmo|algoritmo]] basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
+'''QuickSort''' (en inglés, ordenamiento rápido). Es un [[Algoritmo|algoritmo]] basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
 == Descripción del algoritmo  ==
@@ Línea 97: / Línea 98: @@
 *WEISS, M. A., Estructuras de datos y algoritmos. Addison-Wesley Iberoamericana, 1995.
 *WIRTH, Niklaus. Algoritmos y Estructuras de Datos. Pentice Hall, 1987.
+</div>
 [[Category:Algoritmos]]

← Revisión anterior	Revisión del 04:04 22 feb 2012
(Sin diferencias)

@@ Línea 1: / Línea 1: @@
 {{Definición
 |nombre=Ordenamiento por Quicksort
-|imagen=Quicksort.gif
+|imagen=Algo_Quicksort.gif
 |tamaño=
 |concepto=

QuickSort - Historial de revisiones

Carlos idict: Texto reemplazado: «» por «»

Yalexy idict: /* Descripción del algoritmo */

Astroboy: /* Descripción del algoritmo */

Astroboy en 04:28 22 feb 2012

Astroboy en 04:26 22 feb 2012

Astroboy: Ordenamiento por Quicksort trasladada a QuickSort

Manuel jc.manzanillo1 en 23:39 29 jul 2011

Rolando01015jc en 13:09 5 abr 2011

Rolando01015jc en 13:01 5 abr 2011

Rolando01015jc: Página creada con '{{Definición |nombre=Ordenamiento por Quicksort |imagen=Quicksort.gif |tamaño= |concepto= }} '''El ordenamiento rápido,''' '''quicksort '''en inglés: Es un [[...'

Carlos idict: Texto reemplazado: «
» por «»