Diferencia entre revisiones de «Estructuras de datos dinámicas/Algoritmos de ordenamiento»
Contenido eliminado Contenido añadido
Sin resumen de edición |
Sin resumen de edición |
||
Línea 3:
== Quicksort ==
Quicksort es un algoritmo de ordenamiento que utiliza la técnica 'divide y vencerás'. Consiste en dividir la secuencia a ser ordenada en dos partes, de tal manera que cada unos de los elementos de una de las partes sea mayor o igual a todos los elementos de la segunda parte. Cada una de las partes se divide y se le aplica a su vez este procedimiento recursivamente, hasta llegar a las secuencias unitarias. Al finalizar este procedimiento, la secuencia completa queda ordenada.
=== Algoritmo ===
# Elegir un elemento de la secuencia, llamado ''pivote''.
# Reordenar la secuencia de tal manera que los elementos menores que
# Ordenar recursivamente las subsecuencias.
Línea 39:
==== Versión de ordenamiento sin espacio de almacenamiento adicional ====
La desventaja de la versión precedente es que requiere un almacenamiento extra de <math>
public static void quickSort(List secuencia, int indiceInferior, int indiceSuperior)
Línea 61:
{
quickSort(secuencia,0,secuencia.size());
return secuencia
}
=== Análisis ===
En el mejor de los casos, en cada paso se dividirá la secuencia en dos partes, de manera que la profundidad del árbol de llamadas iterativas será<math>\log_2n </math>, y como la cantidad de elementos a ser
En el peor caso, en cada paso se produce una partición completamente desbalanceada, es decir, queda un solo elemento de un lado, y el resto del otro lado, por lo que se debe iterar en cada paso <math>i</math> con <math>n - i</math>, lo que requerirá <math>n!</math> iteraciones: el orden de la complejidad del algoritmo será <math>O (n^2)</math>.
Como para una distribución uniforme de los datos, el caso se asemejará mucho más al primero, se dice que el orden de la complejidad promedio del algoritmo es <math>\Theta (n \log n)</math>.
| |||