En este artículo, discutiremos propiedades importantes de diferentes técnicas de ordenación incluyendo su complejidad, estabilidad y restricciones de memoria. Antes de entender este artículo, usted debe entender los fundamentos de las diferentes técnicas de ordenación (Ver : Técnicas de Ordenación).
Análisis de la complejidad del tiempo –
Hemos discutido el mejor, el promedio y el peor caso de complejidad de las diferentes técnicas de ordenación con los posibles escenarios.
Ordenación basada en la comparación –
En la ordenación basada en la comparación, los elementos de un array se comparan entre sí para encontrar el array ordenado.
- Ordenación por burbuja y ordenación por inserción –
Complejidad temporal media y del peor caso: n^2
Complejidad temporal del mejor caso: n cuando el array ya está ordenado.
Peor caso: cuando el array está ordenado a la inversa. - Selection sort –
Complejidad de tiempo en el mejor, medio y peor caso: n^2 que es independiente de la distribución de los datos. - Ordenación por fusión –
Complejidad de tiempo mejor, media y peor: nlogn que es independiente de la distribución de los datos. - Ordenación por pila –
Complejidad de tiempo mejor, media y peor: nlogn que es independiente de la distribución de los datos. - Ordenación rápida –
Es una aproximación de dividir y conquistar con relación de recurrencia:T(n) = T(k) + T(n-k-1) + cn
Caso peor: cuando el array está ordenado o con ordenación inversa, el algoritmo de partición divide el array en dos subarreglos con 0 y n-1 elementos. Por lo tanto,
T(n) = T(0) + T(n-1) + cnSolving this we get, T(n) = O(n^2)
Caso mejor y caso medio: En promedio, el algoritmo de partición divide el array en dos subarreglos con igual tamaño. Por lo tanto,
T(n) = 2T(n/2) + cnSolving this we get, T(n) = O(nlogn)
Ordenación sin comparación –
En la ordenación sin comparación, los elementos del array no se comparan entre sí para encontrar el array ordenado.
- Ordenación Radix –
Comcomplejidad de tiempo mejor, media y peor: nk donde k es el número máximo de dígitos en los elementos del array. - Ordenación Count –
Complejidad de tiempo mejor, media y peor: n+k donde k es el tamaño del array count. - Ordenación por cubos –
Complejidad de tiempo mejor y media: n+k donde k es el número de cubos.
Complejidad de tiempo en el peor de los casos: n^2 si todos los elementos pertenecen al mismo cubo.
Técnica Inplace/Outplace –
Una técnica de ordenación es inplace si no utiliza memoria extra para ordenar el array.
Entre las técnicas basadas en la comparación discutidas, sólo la ordenación por fusión es una técnica fuera de lugar, ya que requiere una matriz adicional para combinar las submatrices ordenadas.
Entre las técnicas no basadas en la comparación discutidas, todas son técnicas fuera de lugar. La ordenación por conteo utiliza un array de conteo y la ordenación por cubos utiliza una tabla hash para ordenar el array.
Técnica en línea/fuera de línea –
Una técnica de ordenación se considera en línea si puede aceptar nuevos datos mientras el procedimiento está en curso, es decir, no se requieren datos completos para iniciar la operación de ordenación.
Entre las técnicas basadas en la comparación discutidas, sólo la ordenación por inserción cumple este requisito debido al algoritmo subyacente que utiliza, es decir procesa la matriz (no sólo los elementos) de izquierda a derecha y si se añaden nuevos elementos a la derecha, no afecta a la operación en curso.
Técnica estable/inestable –
Una técnica de ordenación es estable si no cambia el orden de los elementos con el mismo valor.
De las técnicas basadas en la comparación, la ordenación por burbujas, la ordenación por inserción y la ordenación por fusión son técnicas estables. La ordenación por selección es inestable ya que puede cambiar el orden de los elementos con el mismo valor. Por ejemplo, consideremos el array 4, 4, 1, 3.
En la primera iteración, el elemento mínimo encontrado es el 1 y se intercambia con el 4 en la posición 0. Por lo tanto, el orden de 4 con respecto a 4 en la 1ª posición cambiará. Del mismo modo, la ordenación rápida y la ordenación de montón también son inestables.
De las técnicas no basadas en la comparación, la ordenación por conteo y la ordenación por cubos son técnicas de ordenación estables, mientras que la estabilidad de la ordenación radix depende del algoritmo subyacente utilizado para la ordenación.
Análisis de las técnicas de ordenación :
- Cuando el array está casi ordenado, se puede preferir la ordenación por inserción.
- Cuando no se conoce el orden de entrada, se prefiere la ordenación por fusión ya que tiene una complejidad temporal en el peor de los casos de nlogn y además es estable.
- Cuando el array está ordenado, la ordenación por inserción y burbuja da una complejidad de n pero la ordenación rápida da una complejidad de n^2.
Que – 1. ¿Qué algoritmo de ordenación tarda menos tiempo cuando todos los elementos de la matriz de entrada son idénticos? Considere las implementaciones típicas de los algoritmos de ordenación.
(A) Ordenación por inserción
(B) Ordenación por montón
(C) Ordenación por fusión
(D) Ordenación por selección
Solución: Como se ha comentado, la ordenación por inserción tendrá la complejidad de n cuando el array de entrada ya esté ordenado.
Que – 2. Considere el algoritmo Quicksort. Supongamos que existe un procedimiento para encontrar un elemento pivote que divide la lista en dos sublistas, cada una de las cuales contiene al menos una quinta parte de los elementos. Sea T(n) el número de comparaciones necesarias para ordenar n elementos. Entonces, (GATE-CS-2012)
(A) T(n) <= 2T(n/5) + n
(B) T(n) <= T(n/5) + T(4n/5) + n
(C) T(n) <= 2T(4n/5) + n
(D) T(n) <= 2T(n/2) + n
Solución: La complejidad de la ordenación rápida puede escribirse como:
T(n) = T(k) + T(n-k-1) + cn
Como se indica en la pregunta, una lista contiene 1/5 del total de elementos. Por lo tanto, otra lista tendrá 4/5 del total de elementos. Poniendo valores, obtenemos:
T(n) = T(n/5) + T(4n/5) + cn, que coincide con la opción (B).
Tabla de comparación de la complejidad temporal y espacial :
| Algoritmo de ordenación | Complejidad temporal | Complejidad espacial | ||
|---|---|---|---|---|
| Caso mejor | Promedio. Caso | El peor caso | El peor caso | |
| Ordenación por burbujas | Ω(N) | Θ(N2) | O(N2) | O(1) |
| Ordenación por selección | Ω(N2) | Θ(N2) | O(N2) | O(1) |
| Ordenación por inserción | Ω(N) | Θ(N2) | O(N2) | O(1) |
| Merge Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(N) |
| Heap Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(1) |
| Ordenación rápida | Ω(N log N) | Θ(N log N) | O(N2) | O(N log N) |
| Ordenación radial | Ω(N k) | Θ(N k) | O(N k) | O(N + k) |
| Count Sort | Ω(N + k) | Θ(N + k) | O(N + k) | O(k) |
| Bucket Sort | Ω(N + k) | Θ(N + k) | O(N2) | O(N) |
