Análisis de diferentes técnicas de clasificación.

En este artículo, discutiremos propiedades importantes de diferentes técnicas de clasificación, incluida su complejidad, estabilidad y restricciones de memoria. Antes de comprender este artículo, debe comprender los conceptos básicos de las diferentes técnicas de clasificación (consulte: Técnicas de clasificación ). 

Análisis de la complejidad del tiempo: 
hemos discutido la complejidad del mejor, el promedio y el peor de los casos de diferentes técnicas de clasificación con posibles escenarios. 

Clasificación basada en comparación: 
en la clasificación basada en comparación, los elementos de una array se comparan entre sí para encontrar la array ordenada. 

• Ordenación por burbuja y ordenación por inserción 
  : complejidad de tiempo promedio y en el peor de los casos: n^2 
  Complejidad de tiempo en el mejor de los casos: n cuando la array ya está ordenada. 
  En el peor de los casos: cuando la array se ordena de forma inversa. 
   
• Clasificación de selección 
  : complejidad de tiempo del mejor, promedio y peor caso: n ^ 2 que es independiente de la distribución de datos. 
   
• Merge sort – 
  Complejidad de tiempo en el mejor, promedio y peor de los casos: nlogn que es independiente de la distribución de datos. 
   
• Heap sort – 
  Mejor, promedio y peor complejidad de tiempo: nlogn que es independiente de la distribución de datos. 
   
• Clasificación rápida: 
  es un enfoque de divide y vencerás con una relación de recurrencia: 
   

 T(n) = T(k) + T(n-k-1) + cn

• En el peor de los casos: cuando la array se ordena o se ordena inversamente, el algoritmo de partición divide la array en dos subarreglos con 0 y n-1 elementos. Por lo tanto, 
   

T(n) = T(0) + T(n-1) + cn
Solving this we get, T(n) = O(n^2)

• Mejor caso y caso promedio: en promedio, el algoritmo de partición divide la array en dos subarreglos con el mismo tamaño. Por lo tanto, 
   

T(n) = 2T(n/2) + cn
Solving this we get, T(n) = O(nlogn)

Clasificación no basada en comparación: en la clasificación 
no basada en comparación, los elementos de la array no se comparan entre sí para encontrar la array ordenada. 
 

• Radix sort – 
  Mejor, promedio y peor complejidad temporal: nk donde k es el número máximo de dígitos en los elementos de la array. 
   
• Clasificación 
  de conteo: complejidad de tiempo del mejor, promedio y peor caso: n+k donde k es el tamaño de la array de conteo. 
   
• Tipo de cubeta 
  : complejidad de tiempo mejor y promedio: n+k donde k es el número de cubetas. 
  Complejidad de tiempo en el peor de los casos: n^2 si todos los elementos pertenecen al mismo depósito. 
   

Técnica in-place/Outplace: 
una técnica de clasificación está en su lugar si no utiliza ninguna memoria adicional para clasificar la array. 
Entre las técnicas basadas en la comparación discutidas, solo la ordenación por fusión es la técnica superada, ya que requiere una array adicional para fusionar las subarreglas ordenadas. 
Entre las técnicas no basadas en la comparación discutidas, todas son técnicas superadas. La ordenación por conteo usa una array de conteo y la ordenación por cubo usa una tabla hash para ordenar la array. 

Técnica en línea/fuera de línea: 
una técnica de clasificació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 clasificación. 
Entre las técnicas basadas en comparación discutidas, solo la ordenación por inserción califica para esto debido al algoritmo subyacente que utiliza, es decir, procesa la array (no solo los elementos) de izquierda a derecha y si se agregan nuevos elementos a la derecha, no afecta el operación en curso. 

Técnica estable/inestable: 
una técnica de clasificación es estable si no cambia el orden de los elementos con el mismo valor. 
Fuera de las técnicas basadas en la comparación, la clasificación por burbujas, la clasificación por inserción y la clasificació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, considere la array 4, 4, 1, 3. 

En la primera iteración, el elemento mínimo encontrado es 1 y se intercambia con 4 en la posición 0. Por lo tanto, cambiará el orden de 4 con respecto a 4 en la 1ra posición. Del mismo modo, la ordenación rápida y la ordenación en montón también son inestables. 

Fuera de las técnicas que no se basan en la comparación, la clasificación por conteo y la clasificación por cubos son técnicas de clasificación estables, mientras que la estabilidad de la clasificación por radix depende del algoritmo subyacente utilizado para la clasificación. 

Análisis de técnicas de clasificación: 
 

• Cuando la array está casi ordenada, se puede preferir la ordenación por inserción.
• Cuando no se conoce el orden de entrada, se prefiere la ordenación por combinación, ya que tiene una complejidad de tiempo de nlogn en el peor de los casos y también es estable.
• Cuando se ordena la array, la inserción y la ordenación de burbujas dan una complejidad de n, pero la ordenación rápida da una complejidad de n^2.

Que – 1. ¿Qué algoritmo de clasificación tardará menos tiempo cuando todos los elementos de la array de entrada sean idénticos? Considere implementaciones típicas de algoritmos de clasificación. 
(A) Clasificación por inserción 
(B) Clasificación en montón 
(C) Clasificación por fusión 
(D) Clasificación por selección 

Solución: como se discutió, la ordenación por inserción tendrá la complejidad de n cuando la array de entrada ya esté ordenada. 

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 clasificar 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 se puede escribir 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 complejidad de tiempo y espacio:

Algoritmo de clasificación	Complejidad del tiempo			Complejidad espacial
	Mejor caso	Caso promedio	Peor de los casos	Peor de los casos
Ordenamiento de burbuja	Ω(N)	Θ(N 2 )	O(N 2 )	O(1)
Clasificación de selección	Ω(N 2 )	Θ(N 2 )	O(N 2 )	O(1)
Tipo de inserción	Ω(N)	Θ(N 2 )	O(N 2 )	O(1)
Ordenar por fusión	Ω(N registro N)	Θ(N log N)	O(N registro N)	EN)
Ordenar montón	Ω(N registro N)	Θ(N log N)	O(N registro N)	O(1)
Ordenación rápida	Ω(N registro N)	Θ(N log N)	O(N 2 )	O (registro N)
Clasificación Radix	Ω(Nk)	Θ(Nk)	O(Nk)	O(N + k)
Ordenar conteo	Ω(N + k)	Θ(N + k)	O(N + k)	OK)
Clasificación de cubo	Ω(N + k)	Θ(N + k)	O(N 2 )	EN)