If you're seeing this message, it means we're having trouble loading external resources on our website.

Si estás detrás de un filtro de páginas web, por favor asegúrate de que los dominios *.kastatic.org y *.kasandbox.org estén desbloqueados.

Contenido principal

Curso: Ciencias de la computación > Unidad 1

Lección 9: Ordenamiento rápido
Computación
Ciencias de la computación
Algoritmos
Ordenamiento rápido
© 2024 Khan AcademyTérminos de usoPolítica de privacidadAviso de cookies

Vista general del ordenamiento rápido

Google Classroom
Como el ordenamiento por mezcla, el ordenamiento rápido utiliza divide y vencerás, así que es un algoritmo recursivo. La manera en que el ordenamiento rápido utiliza divide y vencerás es un poco diferente de como lo hace el ordenamiento por mezcla. En el ordenamiento por mezcla, el paso de dividir casi no hace nada, y todo el trabajo real ocurre en el paso de combinar. El ordenamiento rápido es lo contrario: todo el trabajo real ocurre en el paso de dividir. De hecho, el paso de combinar en el ordenamiento rápido no hace absolutamente nada.
El ordenamiento rápido tiene un par de otras diferencias con el ordenamiento por mezcla. El ordenamiento rápido funciona en el lugar y el tiempo de ejecución para el peor caso es tan malo como el del ordenamiento por selección y el de inserción: Θ(n2). Pero el tiempo de ejecución de su caso promedio es tan bueno como el del ordenamiento por mezcla: Θ(nlog2⁡n).
Entonces, ¿por qué pensar acerca del ordenamiento rápido cuando el ordenamiento por mezcla es al menos igual de bueno? Esto se debe a que el factor constante oculto en la notación Θ grande para el ordenamiento rápido es bastante bueno. En la práctica, el ordenamiento rápido supera al ordenamiento por mezcla y supera de manera significativa al ordenamiento por selección y por inserción.
Aquí está cómo el ordenamiento rápido usa divide y vencerás. Como con el ordenamiento por mezcla, piensa en ordenar un subarreglo array[p..r], donde inicialmente el subarreglo es array[0..n-1].
  1. Divide el elegir cualquier elemento en el subarreglo array[p..r]. Llama a este elemento el pivote.
    Reorganiza los elementos en array[p..r] de modo que todos los elementos en ese array[p..r] que sean menores o iguales que el pivote estén a su izquierda y todos los elementos que sean mayores que el pivote estén a su derecha. A este procedimiento lo llamamos partición. En este punto, no importa en qué orden estén los elementos a la izquierda del pivote entre sí, y lo mismo se aplica para los elementos a la derecha del pivote. Solo nos importa que cada elemento esté en algún lugar del lado correcto del pivote.
    Como una cuestión práctica, siempre vamos a escoger el elemento de hasta la derecha en el subarreglo, array[r], como el pivote. Así que, por ejemplo, si el subarreglo consiste de [9, 7, 5, 11, 12, 2, 14, 3, 10, 6], entonces escogemos 6 como el pivote. Después de hacer la partición, el subarreglo podría verse como [5, 2, 3, 6, 12, 7, 14, 9, 10, 11]. Sea q el índice de dónde está el pivote.
  2. Vence al ordenar de manera recursiva los subarreglos array[p..q-1] (todos los elementos a la izquierda del pivote, los cuales deben ser menores o iguales que el pivote) y array[q+1..r] (todos los elementos a la derecha del pivote, los cuales deben ser mayores que el pivote).
  3. Combina al hacer nada. Una vez que el paso de conquistar ordena de manera recursiva, ya terminamos. ¿Por qué? Todos los elementos a la izquierda del pivote, en array[p..q-1], son menores o iguales que el pivote y están ordenados, y todos los elementos a la derecha del pivote, en array[q+1..r], son mayores que el pivote y están ordenados. ¡Los elementos en array[p..r] tienen que estar ordenados!
    Piensa acerca de nuestro ejemplo. Después de ordenar de manera recursiva los subarreglos a la izquierda y a la derecha del pivote, el subarreglo a la izquierda del pivote es [2, 3, 5], y el subarreglo a la derecha del pivote es [7, 9, 10, 11, 12, 14]. Así que el subarreglo tiene [2, 3, 5], seguido de 6, seguido de [7, 9, 10, 11, 12, 14]. El subarreglo está ordenado.
Los casos base son subarreglos con menos de dos elementos, justo como en el ordenamiento por mezcla. En el ordenamiento por mezcla nunca ves un subarreglo sin elementos, pero si puedes verlos en el ordenamiento rápido si los otros elementos en el subarreglo son todos menores que el pivote o son todos mayores que el pivote.
Volvamos al paso de vencer y recorramos el ordenamiento recursivo de los subarreglos. Después de hacer la primera partición tenemos los subarreglos [5, 2, 3] y [12, 7, 14, 9, 10, 11], con 6 como el pivote.
Para ordenar el subarreglo [5, 2, 3], escogemos a 3 como el pivote. Después de hacer la partición, tenemos [2, 3, 5]. El subarreglo [2], a la izquierda del pivote, es un caso base cuando hacemos recursividad, como lo es el subarreglo [5], a la derecha de pivote.
Para ordenar el subarreglo [12, 7, 14, 9, 10, 11], elegimos 11 como el pivote. Después de hacer la partición, tenemos [7, 9, 10] a la izquierda del pivote y [14, 12] a la derecha. Entonces los subarreglos están ordenados, resultando en [7, 9, 10], seguido por 11, seguido por [12, 14].
Aquí está cómo se desarrolla todo el algoritmo del ordenamiento rápido. Las ubicaciones de los arreglos en azul han sido pivotes en llamadas recursivas anteriores, así que los valores en estas ubicaciones no se van a volver a examinar o mover:
Un diagrama que muestra cinco pasos para ordenar un arreglo usando el ordenamiento rápido.
  1. El arreglo comienza con los elementos [9, 7, 5, 11, 12, 2, 14, 3, 10, 6], con el índice p que apunta al primer elemento y el índice r, al último elemento.
  2. Los elementos del arreglo ahora están ordenados como [5, 2, 3, 6, 12, 7, 14, 9, 10, 11]. El arreglo ahora tiene un índice q que apunta al cuarto elemento que contiene el valor 6.
  3. Los elementos del arreglo ahora están ordenados como [2, 3, 5, 6, 7, 9, 10, 11, 14, 12]. El arreglo ahora tiene varios índices llamados p, q y r. La primera p apunta al primer elemento, la primera q apunta al segundo elemento, la primera r apunta al tercer elemento. La segunda p apunta al quinto elemento, la segunda q apunta al octavo elemento y la segunda p apunta al elemento final.
  4. Los elementos del arreglo ahora están ordenados como [2, 3, 5, 6, 7, 9, 10, 11, 12, 14]. El primer par de p y r apuntan al primer elemento, el segundo par de p y r apuntan al tercer elemento. La tercera p apunta al quinto elemento, una q y la tercera r apuntan al séptimo elemento. La cuarta p y una q apuntan al noveno elemento y la cuarta r apunta al último elemento.
  5. Los elementos del arreglo siguen ordenados como [2, 3, 5, 6, 7, 9, 10, 11, 12, 14]. La primera p apunta al quinto elemento, la primera q y la primera r apuntan al sexto elemento. Un par de p y r apuntan al último elemento.
  6. Los elementos del arreglo siguen ordenados como [2, 3, 5, 6, 7, 9, 10, 11, 12, 14]. Un solo par de p y r apuntan al quinto elemento.
Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.

¿Quieres unirte a la conversación?

Inicia sesión
¿Sabes inglés? Haz clic aquí para ver más discusiones en el sitio en inglés de Khan Academy.