Resumen de Ordenamiento rápido (quicksort)
Ordenamiento Rápido (Quicksort): Guía Completa para Estudiantes
Algoritmo Quicksort: Una Introducción Completa
El Ordenamiento Rápido, o Quicksort, es uno de los algoritmos de ordenamiento más eficientes y usados en informática. Fue creado por Tony Hoare en 1959 y se basa en el principio de "divide y vencerás". Esto significa que descompone un problema grande en partes más pequeñas y manejables, resuelve esas partes, y luego combina las soluciones para resolver el problema original.
Principio de Funcionamiento
La idea principal de Quicksort es seleccionar un elemento de la lista, llamado pivote, y reorganizar los demás elementos de la lista. Todos los elementos menores que el pivote se colocan antes que él, y todos los mayores se colocan después. Este proceso se llama partición. Una vez que el pivote está en su posición final, el algoritmo se aplica recursivamente a las dos sublistas (la de elementos menores y la de elementos mayores) hasta que toda la lista esté ordenada. El algoritmo finaliza cuando una sublista tiene cero o un elemento, ya que estas listas se consideran ordenadas por definición.
Pivote: Un elemento de la lista que se utiliza como punto de referencia para dividir la lista en dos sublistas: una con elementos menores y otra con elementos mayores que él.
Partición: El proceso de reorganizar los elementos de una sublista alrededor de un pivote, de modo que todos los elementos menores o iguales al pivote estén antes que él, y todos los mayores estén después.
El Proceso de Partición: Esquema de Lomuto
Hay varias maneras de implementar la partición, pero el esquema de Lomuto es uno de los más fáciles de entender. Este esquema elige el último elemento de la sublista como pivote. Luego, recorre la sublista con un puntero $j$ desde el inicio hasta el elemento justo antes del pivote. Otro puntero $i$ lleva la cuenta del final de la sección de elementos menores o iguales al pivote.
Los pasos del esquema de partición de Lomuto son los siguientes:
- Se elige un elemento como pivote. En el esquema de Lomuto, tradicionalmente se selecciona el último elemento de la sublista, es decir, $arr[alto]$.
- Se inicializa un índice $i$ (índice del elemento más pequeño) a $bajo - 1$.
- Se recorre la sublista con un índice $j$ desde $bajo$ hasta $alto - 1$.
- Si $arr[j]$ es menor o igual que el pivote: a. Se incrementa $i$. b. Se intercambian $arr[i]$ y $arr[j]$.
- Después de que el bucle termina, se intercambia $arr[i + 1]$ con el pivote ($arr[alto]$).
- La función de partición devuelve el índice $i + 1$, que es la posición final del pivote.
Ejemplo Detallado de Partición de Lomuto
Consideremos la siguiente lista de números enteros: $[7, 2, 1, 6, 8, 5, 3, 4]$. Vamos a aplicar el esquema de partición de Lomuto con $bajo = 0$ y $alto = 7$.
-
Selección del pivote: El pivote es el último elemento, $arr[7] = 4$.
-
Inicialización: $i = bajo - 1 = 0 - 1 = -1$.
-
Recorrido con $j$ desde $0$ hasta $6$ ($alto - 1$):
- j = 0: $arr[0] = 7$. ¿$7 \le 4$? No. La lista permanece $[7, 2, 1, 6, 8, 5, 3, 4]$. $i = -1$.
- j = 1: $arr[1] = 2$. ¿$2 \le 4$? Sí. Se incrementa $i$ a $0$. Se intercambian $arr[0]$ y $arr[1]$. La lista se convierte en $[2, 7, 1, 6, 8, 5, 3, 4]$. $i = 0$.
- j = 2: $arr[2] = 1$. ¿$1 \le 4$? Sí. Se incrementa $i$ a $1$. Se intercambian $arr[1]$ y $arr[2]$. La lista se convierte en $[2, 1, 7, 6, 8, 5, 3, 4]$. $i = 1$.
- j = 3: $arr[3] = 6$. ¿$6 \le 4$? No. La lista permanece $[2, 1, 7, 6, 8, 5, 3, 4]$. $i = 1$.
- j = 4: $arr[4] = 8$. ¿$8 \le 4$? No. La lista permanece $[2, 1, 7, 6, 8, 5, 3, 4]$. $i = 1$.
- j = 5: $arr[5] = 5$. ¿$5 \le 4$? No. La lista permanece $[2, 1, 7, 6, 8, 5, 3, 4]$. $i = 1$.
- j = 6: $arr[6] = 3$. ¿$3 \le 4$? Sí. Se incrementa $i$ a $2$. Se intercambian $arr[2]$ y $arr[6]$. La lista se convierte en $[2, 1, 3, 6, 8, 5, 7, 4]$. $i = 2$.
-
Fin del bucle. Ahora $i = 2$. Se intercambia $arr[i + 1]$ (que es $arr[3] = 6$) con el
Regístrate para el resumen completo¿Ya tienes cuenta? Iniciar sesión
Algoritmo Quicksort
Klíčová slova: Algoritmo Quicksort
Klíčové pojmy: Quicksort es un algoritmo de ordenamiento que utiliza el paradigma "divide y vencerás"., La operación central de Quicksort es la **partición**, que reubica elementos alrededor de un **pivote**., El esquema de partición de Lomuto utiliza el último elemento como pivote y reordena la sublista en su lugar., La **elección del pivote** es crucial; una mala elección puede degradar el rendimiento al peor caso., Estrategias de pivote incluyen primer, último, central, mediana de tres, o aleatorio., La complejidad temporal promedio de Quicksort es $O(n \log n)$., La complejidad temporal en el peor caso de Quicksort es $O(n^2)$., La complejidad espacial promedio de Quicksort es $O(\log n)$ debido a las llamadas recursivas., Quicksort es un algoritmo de ordenamiento *in situ* (o casi *in situ*)., Errores comunes incluyen confundir el pivote o implementar la partición incorrectamente., Las simulaciones interactivas son herramientas valiosas para visualizar y entender el funcionamiento de Quicksort.