Ordenación rápida

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 17 de enero de 2020; las comprobaciones requieren 63 ediciones .
Ordenación rápida

Visualización del algoritmo quicksort. Las líneas horizontales representan elementos de referencia.
Autor Hoare, Charles Anthony Richard [1]
objetivo Algoritmo de clasificación
peor momento O( n 2 )
Mejor tiempo O( n log n ) (división normal)
u O( n ) (tripartición)
Tiempo promedio O( n registro n )
costo de memoria O( n ) ayudantes
O(log n ) ayudantes (Sedgwick 1978)
 Archivos multimedia en Wikimedia Commons

La clasificación rápida, la clasificación de Hoare ( eng.  quicksort ), a menudo llamada qsort (después del nombre en la biblioteca estándar de C ) es un algoritmo de clasificación desarrollado por el científico informático inglés Tony Hoare durante su trabajo en STU en 1960 .

Uno de los algoritmos de clasificación de matrices universales más rápidos conocidos: en promedio intercambios al ordenar elementos; Debido a la presencia de una serie de deficiencias en la práctica, generalmente se usa con algunas modificaciones.

Descripción general

QuickSort es una versión significativamente mejorada del algoritmo de clasificación de intercambio directo (cuyas variantes se conocen como " Bubble Sort " y " Shaker Sort "), que también es conocido por su baja eficiencia. La diferencia fundamental es que primero se realizan las permutaciones más grandes posibles y, después de cada pasada, los elementos se dividen en dos grupos independientes (por lo tanto, mejorar el método de clasificación directa más ineficiente resultó en uno de los métodos mejorados más eficientes).

La idea general del algoritmo es la siguiente:

En la práctica, la matriz generalmente no se divide en tres, sino en dos partes: por ejemplo, "referencia más pequeña" e "igual y mayor"; este enfoque es generalmente más eficiente, ya que simplifica el algoritmo de separación (ver más abajo).

Hoare desarrolló este método en relación con la traducción automática ; el diccionario se almacenó en cinta magnética , y la clasificación de las palabras del texto procesado hizo posible obtener sus traducciones en una sola pasada de la cinta, sin rebobinarla. El algoritmo fue inventado por Hoare durante su estancia en la Unión Soviética , donde estudió traducción informática en la Universidad de Moscú y desarrolló un libro de frases ruso-inglés.

Algoritmo

Mecanismo general de clasificación

Quicksort se refiere a los algoritmos de " divide y vencerás ".

El algoritmo consiste de tres pasos:

  1. Seleccione un elemento de una matriz. Llamémoslo base.
  2. Dividir : reorganizar los elementos en una matriz para que los elementos menores que el pivote se coloquen antes y los mayores o iguales se coloquen después.
  3. Aplique recursivamente los primeros dos pasos a los dos subarreglos a la izquierda y derecha del pivote. La recursividad no se aplica a una matriz que tiene solo un elemento o ningún elemento.

En la forma más general, el algoritmo de pseudocódigo (donde A es la matriz que se ordenará, y bajo y alto son los límites inferior y superior de la sección ordenada de esta matriz, respectivamente) se ve así:

algoritmo quicksort(A, bajo, alto) es si bajo <alto entonces p:= partición(A, bajo, alto) clasificación rápida (A, bajo, p) clasificación rápida (A, p + 1, alta)

Aquí se supone que la matriz A se pasa por referencia, es decir, la clasificación ocurre "en el mismo lugar", y la función de partición indefinida devuelve el índice del elemento pivote.

Existen diferentes enfoques para la selección del elemento pivote y la operación de partición que afectan el rendimiento del algoritmo.

También es posible la siguiente implementación de quicksort:

el algoritmo quicksort(A) es si A está vacío, devuelve A pivot:= A.pop() (extrae el último o el primer elemento de la matriz) lA:= A.filter(donde e <= pivote) (crear matriz con elementos menores que pivote) rA := A.filter(donde e > pivote) (crear matriz con elementos mayores que pivote) return quicksort(lA) + [pivot] + quicksort(rA) (devuelve una matriz que consiste en el lado izquierdo ordenado, el pivote y el lado derecho ordenado).

En la práctica, no se usa, pero sirve solo con fines educativos, ya que usa memoria adicional, que se puede evitar.

Selección de elementos de referencia

En las primeras implementaciones, por regla general, el primer elemento se elegía como referencia, lo que reducía el rendimiento en las matrices ordenadas. Para mejorar la eficiencia, se puede elegir el elemento aleatorio medio o (para arreglos grandes) la mediana de los elementos primero, medio y último. [3] La mediana de toda la secuencia es un pivote óptimo, pero su cálculo requiere demasiado tiempo para utilizarlo en la clasificación.

Seleccionando un pivote por la mediana de tres para la partición de Lomuto:

medio := (bajo + alto) / 2 si A[medio] < A[bajo] intercambiar A[bajo] con A[medio] si A[alto] < A[bajo] intercambiar A[bajo] con A[alto] si A[alto] < A[medio] intercambiar A [alto] con A [medio] pivote:= A[medio]

Partición Lomuto

Este algoritmo de partición fue propuesto por Nico Lomuto [4] y popularizado en los libros de Bentley (Programming Pearls) y Cormen (Introduction to Algorithms). [5] En este ejemplo, el último elemento se selecciona como pivote. El algoritmo almacena el índice en la variable i . Cada vez que se encuentra un elemento que es menor o igual que el pivote, el índice se incrementa y el elemento se inserta antes del pivote. Aunque este esquema de partición es más simple y compacto que el esquema de Hoare, es menos eficiente y se usa en tutoriales. La complejidad de este ordenamiento rápido aumenta a O ( n2 ) cuando la matriz ya está ordenada o todos sus elementos son iguales. Existen varios métodos para optimizar esta clasificación: algoritmos de selección de pivote, utilizando la clasificación por inserción en matrices pequeñas. En este ejemplo, los elementos de la matriz A se ordenan de menor a mayor (inclusive) [5] :

la partición del algoritmo (A, bajo, alto) es pivote := A[alto] yo := bajo para j := bajo a alto - 1 hacer si A[j] ≤ pivote entonces intercambiar A[i] con A[j] yo := yo + 1 intercambiar A[i] con A[high] vuelvo yo

Se puede ordenar una matriz completa haciendo quicksort(A, 1, length(A)) .

Partiendo Hoare

Este esquema utiliza dos índices (uno al principio de la matriz, el otro al final), que se aproximan entre sí hasta que hay un par de elementos donde uno es mayor que el pivote y está ubicado antes de él, y el segundo es más pequeño y ubicado después de este. Estos elementos se intercambian. El intercambio ocurre hasta que los índices se cruzan. El algoritmo devuelve el último índice. [6] El esquema de Hoare es más eficiente que el esquema de Lomuto, ya que en promedio hay tres veces menos intercambios (swap) de elementos, y la partición es más eficiente incluso cuando todos los elementos son iguales. [7] Similar al esquema de Lomuto, este esquema también muestra la eficiencia O ( n2 ) cuando la matriz de entrada ya está ordenada. Ordenar usando este esquema es inestable. Tenga en cuenta que la posición final del elemento ancla no es necesariamente la misma que el índice devuelto. Pseudocódigo [5] :

algoritmo quicksort(A, lo, hola) es si lo <hi entonces p:= partición(A, bajo, hola) clasificación rápida (A, lo, p) clasificación rápida (A, p + 1, hola) la partición del algoritmo (A, bajo, alto) es pivote:= A[(bajo + alto) / 2] yo:= bajo j:= alto bucle para siempre mientras que A[i] < pivote yo:= yo + 1 mientras que A[j] > pivote j:= j-1 si i >= j entonces regresa j intercambia A[i++] con A[j--]

El libro [5] menciona que tal implementación del algoritmo tiene "muchos puntos sutiles". Aquí hay uno: seleccionar un elemento ya existente en la matriz como elemento de referencia puede provocar un desbordamiento de la pila de llamadas debido al hecho de que el número del elemento se calcula como un promedio, que no es un número entero. Por lo tanto, es más lógico en este algoritmo elegir el valor medio entre los elementos inicial y final como elemento de referencia:

pivote := (A[bajo] + A[alto])/2


Elementos recurrentes

Para mejorar el rendimiento con una gran cantidad de elementos idénticos en la matriz, se puede aplicar el procedimiento para dividir la matriz en tres grupos: elementos menores que la referencia, iguales y mayores. (Bentley y McIlroy llaman a esto una "partición gruesa". Esta partición se usa en la función qsort en Unix 7 [8] ). Pseudocódigo:

algoritmo quicksort(A, bajo, alto) es si bajo <alto entonces p := pivote(A, bajo, alto) izquierda, derecha := partición(A, p, bajo, alto) // devuelve dos valores clasificación rápida (A, bajo, izquierda) clasificación rápida (A, derecha, alta)

Quicksort se utiliza en el estándar de lenguaje C++, en particular en el método de clasificación de la estructura de datos de lista.

#incluir <iostream> #incluir <lista> int principal () { // ordenación rápida std :: lista < int > lista ; const int N = 20 ; para ( int i = 0 ; i < N ; i ++ ) { si ( yo % 2 == 0 ) lista _ push_back ( N - i ); más lista _ empujar_frente ( N - i ); } for ( std :: list < int >:: iterator it = list . begin (); it != list . end (); it ++ ) { std :: cout << ( * it ) << " " ; } std :: cout << std :: endl ; lista _ ordenar (); for ( std :: list < int >:: iterator it = list . begin (); it != list . end (); it ++ ) { std :: cout << ( * it ) << " " ; } // fin de clasificación rápida std :: cout << std :: endl ; // ordenar mayor lista _ ordenar ( std :: mayor < int > ()); for ( std :: list < int >:: iterator it = list . begin (); it != list . end (); it ++ ) { std :: cout << ( * it ) << " " ; } std :: cout << std :: endl ; // ordena el final mayor estándar :: cin . ignorar (); }

Estimación de la complejidad de un algoritmo

Está claro que la operación de dividir un arreglo en dos partes con respecto al elemento de referencia lleva su tiempo . Dado que todas las operaciones de partición realizadas a la misma profundidad de recursión procesan diferentes partes de la matriz original, cuyo tamaño es constante, en total, también se requerirán operaciones en cada nivel de recursión. Por lo tanto, la complejidad general del algoritmo está determinada únicamente por el número de divisiones, es decir, la profundidad de la recursividad. La profundidad de la recursividad, a su vez, depende de la combinación de datos de entrada y de cómo se determina el pivote.

Mejor caso. En la versión más equilibrada, en cada operación de división, la matriz se divide en dos partes idénticas (más o menos un elemento), por lo tanto, la profundidad de recursión máxima a la que los tamaños de las subarreglas procesadas alcanzan 1 será . Como resultado, el número de comparaciones realizadas por quicksort sería igual al valor de la expresión recursiva , que da la complejidad general del algoritmo . Promedio. La complejidad promedio con una distribución aleatoria de datos de entrada solo puede estimarse probabilísticamente. En primer lugar, debe tenerse en cuenta que en realidad no es necesario que el elemento de pivote divida la matriz en dos partes idénticas cada vez. Por ejemplo, si en cada etapa habrá una división en arreglos con una longitud de 75% y 25% del original, la profundidad de recursión será igual a , y esto aún da complejidad . En general, para cualquier relación fija entre las partes izquierda y derecha de la división, la complejidad del algoritmo será la misma, solo que con diferentes constantes. Consideraremos una división “exitosa” tal que el elemento de referencia estará entre el 50% central de los elementos de la parte compartida del arreglo; claramente, la probabilidad de suerte con una distribución aleatoria de elementos es 0.5. Con una separación exitosa, los tamaños de los subarreglos seleccionados serán al menos el 25 % y no más del 75 % del original. Dado que cada subarreglo seleccionado también tendrá una distribución aleatoria, todas estas consideraciones se aplican a cualquier etapa de clasificación y cualquier fragmento de arreglo inicial. Una división exitosa da una profundidad de recursión de no más de . Dado que la probabilidad de suerte es 0,5, se necesitarán llamadas recursivas en promedio para obtener el elemento pivote k veces en el centro del 50 % de la matriz para obtener divisiones afortunadas. Aplicando estas consideraciones, podemos concluir que en promedio la profundidad de recursión no excederá , que es igual a A ya que no se siguen realizando más operaciones en cada nivel de recursión , la complejidad promedio será . Peor de los casos. En la versión más desequilibrada, cada división produce dos subarreglos de tamaños 1 y , lo que significa que con cada llamada recursiva, el arreglo más grande será 1 más corto que la vez anterior. Esto puede suceder si se selecciona el más pequeño o el más grande de todos los elementos procesados ​​como elemento de referencia en cada etapa. Con la elección más simple de un elemento de referencia, el primero o el último en la matriz, dicho efecto será dado por una matriz ya ordenada (en orden directo o inverso), para el medio o cualquier otro elemento fijo, la "matriz del peor caso". ” también se puede seleccionar especialmente. En este caso , se requerirán operaciones de división y el tiempo total de ejecución serán operaciones, es decir, la clasificación se realizará en tiempo cuadrático. Pero la cantidad de intercambios y, en consecuencia, el tiempo de funcionamiento no es su mayor inconveniente. Peor aún, en este caso, la profundidad de recursión durante la ejecución del algoritmo alcanzará n, lo que significará un ahorro de n veces de la dirección de retorno y las variables locales del procedimiento de partición de la matriz. Para valores grandes de n, el peor de los casos puede provocar el agotamiento de la memoria ( desbordamiento de pila ) mientras se ejecuta el programa.

Ventajas y desventajas

ventajas:

  • Uno de los más rápidos (en la práctica) de los algoritmos de clasificación interna de propósito general.
  • El algoritmo es muy corto: recordando los puntos principales, es fácil escribirlo "desde la cabeza", la constante en es pequeña .
  • Requiere solo memoria adicional para su trabajo (algoritmo recursivo no mejorado, en el peor de los casos de memoria).
  • Combina bien con el almacenamiento en caché y los mecanismos de memoria virtual .
  • Permite la paralelización natural (clasificación de subarreglos asignados en subprocesos paralelos).
  • Permite una modificación eficiente para ordenar por varias claves (en particular, el algoritmo de Sedgwick para ordenar cadenas): debido a que durante el proceso de división se asigna automáticamente un segmento de elementos igual a la referencia, este segmento puede ser ordenado inmediatamente por el siguiente llave.
  • Funciona en listas enlazadas y otras estructuras de acceso secuencial que permiten un recorrido eficiente tanto de principio a fin como de principio a fin.

Defectos:

  • Se degrada fuertemente en velocidad (hasta ) en el peor de los casos o cerca de él, lo que puede suceder con datos de entrada fallidos.
  • Una implementación directa como una función con dos llamadas recursivas puede generar un error de desbordamiento de pila , ya que es posible que deba realizar llamadas recursivas anidadas en el peor de los casos.
  • Inestable _

Mejoras

Las mejoras del algoritmo están destinadas principalmente a eliminar o mitigar las desventajas anteriores, por lo que todas ellas se pueden dividir en tres grupos: hacer que el algoritmo sea estable, eliminar la degradación del rendimiento mediante una elección especial del elemento pivote y proteger contra la pila de llamadas. desbordamiento debido a la gran profundidad de recursión en caso de datos de entrada fallidos.

  • El problema de la inestabilidad se resuelve expandiendo la clave con el índice inicial del elemento en el arreglo. En el caso de igualdad de las claves principales, la comparación se realiza por índice, excluyendo así la posibilidad de cambiar la posición relativa de elementos iguales. Esta modificación no es gratuita: requiere una memoria O(n) adicional y un pase completo a través de la matriz para guardar los índices originales.
  • La degradación de la velocidad en el caso de un conjunto fallido de datos de entrada se resuelve en dos direcciones diferentes: reduciendo la probabilidad de que ocurra el peor de los casos mediante una elección especial del elemento de referencia y el uso de varias técnicas que garantizan un funcionamiento estable en la entrada fallida datos. Para la primera dirección:
  • Selección del elemento central. Elimina la degradación de los datos preordenados, pero deja la posibilidad de ocurrencia aleatoria o selección deliberada de una matriz "mala".
  • Elegir una mediana de tres elementos: primero, medio y último. Reduce la probabilidad de que ocurra el peor de los casos en comparación con elegir el elemento intermedio.
  • Selección aleatoria. La probabilidad de que ocurra al azar el peor de los casos se vuelve extremadamente pequeña y la selección deliberada se vuelve prácticamente imposible. El tiempo de ejecución esperado del algoritmo de ordenación es O( n log n ).
La desventaja de todos los métodos complicados para seleccionar el elemento de referencia es la sobrecarga adicional; sin embargo, no son tan buenos.
  • Para evitar fallas en el programa debido a una gran profundidad de recursión, se pueden usar los siguientes métodos:
  • Cuando se alcance una profundidad de recursividad no deseada, cambie a la clasificación por otros métodos que no requieran recursividad. Un ejemplo de este enfoque es el algoritmo Introsort , o algunas implementaciones de quicksort en la biblioteca STL . Se puede ver que el algoritmo es muy adecuado para este tipo de modificación, ya que en cada etapa le permite seleccionar un segmento continuo de la matriz original destinada a la clasificación, y el método por el cual se clasificará este segmento no afecta el procesamiento de las partes restantes de la matriz.
  • Modificación del algoritmo que elimina una rama de la recursividad: en lugar de llamar recursivamente al procedimiento de división para ambos subarreglos encontrados después de dividir el arreglo, la llamada recursiva se realiza solo para el subarreglo más pequeño, y el más grande se procesa en un bucle dentro del misma llamada de procedimiento . Desde el punto de vista de la eficiencia, en el caso promedio prácticamente no hay diferencia: la sobrecarga para una llamada recursiva adicional y para organizar una comparación de las longitudes de los subarreglos y un ciclo es aproximadamente del mismo orden. Pero la profundidad de recursión bajo ninguna circunstancia excederá , y en el peor de los casos de una división degenerada, generalmente no será más de 2 - todo el procesamiento tendrá lugar en el ciclo del primer nivel de recursión. El uso de este método no lo salvará de una caída catastrófica en el rendimiento, pero no habrá un desbordamiento de pila.
  • Divida la matriz no en dos, sino en tres partes [9] .

Véase también

Notas

  1. ↑ Hoare C. A. R. Algorithm 64: Quicksort  // Commun . ACM - [Nueva York] : Asociación de Maquinaria de Computación , 1961. - Vol. 4, edición. 7.- Pág. 321.- ISSN 0001-0782 ; 1557-7317 - doi:10.1145/366622.366644
  2. ↑ Obviamente, después de tal permutación, para obtener una matriz ordenada, no será necesario mover ninguno de los elementos entre los segmentos resultantes, es decir, será suficiente ordenar los segmentos "más pequeños" y "más grandes". como matrices independientes.
  3. ↑ Sedgewick, Robert Algoritmos en C : fundamentos, estructuras de datos, clasificación, búsqueda, partes 1-4  . — 3. — Educación Pearson, 1998. - ISBN 978-81-317-1291-7 .
  4. ↑ John Bentley. Perlas  de programación . — Addison-Wesley Professional , 1999.
  5. ↑ 1 2 3 4 Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Quicksort // Algoritmos: construcción y análisis = Introducción a los algoritmos / Ed. I. V. Krasikova. - 3ra ed. — M. : Williams, 2013. — S. 170–190. — ISBN 5-8459-1794-8 .
  6. ↑ Hoare, C. a. R. Quicksort  //  El diario de la computadora : diario. - 1962. - 1 de enero ( vol. 5 , no. 1 ). - P. 10-16 . — ISSN 0010-4620 . -doi : 10.1093 / comjnl/5.1.10 .
  7. ↑ Particionamiento Quicksort: Hoare vs. Lomuto . cs.stackexchange.com . Consultado: 3 de agosto de 2015.
  8. ↑ Bentley, John L.; McIlroy, M. Douglas. Ingeniería de una función de clasificación  (inglés)  // Software: práctica y experiencia. - 1993. - vol. 23 , núm. 11 _ - P. 1249-1265 . -doi : 10.1002/ spe.4380231105 .
  9. ↑ Clasificación rápida de doble pivote . Fecha de acceso: 8 de diciembre de 2015. Archivado desde el original el 4 de marzo de 2016.

Literatura

  • Levitin A. V. Capítulo 4. Método de descomposición: Quicksort // Algoritmos. Introducción al desarrollo y análisis - M .: Williams , 2006. - S. 174-179. — 576 pág. — ISBN 978-5-8459-0987-9
  • Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Capítulo 7. Quicksort // Algoritmos: construcción y análisis = Introducción a los algoritmos / Ed. I. V. Krasikova. - 2ª ed. - M. : Williams, 2005. - S. 198-219. — ISBN 5-8459-0857-4 .

Enlaces


 Algoritmos de clasificación
Teoría Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo
Intercambio
Elección
inserciones
fusión
sin comparaciones
híbrido
Otro
poco práctico