Clasificación lenta

Slowsort es un algoritmo de ordenación . Es de naturaleza humorística y poco útil. Es un algoritmo reacio basado en el principio de multiplicar y rendirse (una parodia formada al tomar los opuestos de divide y vencerás ). Fue publicado en 1984 por Andrei Broder y Jorge Stolfi en su artículo "Algoritmos pesimistas y análisis de simplexidad" ^{[ 1 ]} (una parodia de los algoritmos óptimos y el análisis de complejidad ).

Slowsort es un algoritmo recursivo .

• Se ordena in situ .
• Es una ordenación inestable . (Podría cambiar el orden de las claves con el mismo valor).

A continuación se muestra una implementación en pseudocódigo :

procedimiento slowsort ( A [] , start_idx , end_idx ) // Ordena el rango de la matriz A[start ... end] in situ. Si start_idx ≥ end_idx , entonces devuelvemiddle_idx := floor ( ( start_idx + end_idx ) / 2 ) slowsort ( A , start_idx , middle_idx ) // (1.1) slowsort ( A , middle_idx + 1 , end_idx ) // (1.2) if A [ end_idx ] < A [ middle_idx ] then swap ( A , end_idx , middle_idx ) // (1.3)slowsort ( A , start_idx , end_idx - 1 ) // (2)

• Ordena la primera mitad, recursivamente. (1.1)
• Ordena la segunda mitad, recursivamente. (1.2)
• Encuentra el máximo de todo el arreglo comparando los resultados de 1.1 y 1.2, y colócalo al final de la lista. (1.3)
• Ordena toda la lista (excepto el máximo que ahora está al final), de forma recursiva. (2)

Una implementación no optimizada en Haskell (puramente funcional) podría tener el siguiente aspecto:

slowsort :: ( Ord a ) => [ a ] ​​-> [ a ] ​​slowsort xs | length xs <= 1 = xs | otherwise = slowsort xs' ++ [ max llast rlast ] -- (2) donde m = length xs ` div ` 2 l = slowsort $ take m xs -- (1.1) r = slowsort $ drop m xs -- (1.2) llast = last l rlast = last r xs' = init l ++ min llast rlast : init r

La complejidad temporal de Slowsort viene dada por la función${\displaystyle T(n)=2T(n/2)+T(n-1)+1}$Se puede encontrar creando una relación de recurrencia de las llamadas recursivas iniciales (1.1) y (1.2) respectivamente y sumando la llamada recursiva final (2) y modelando las otras operaciones como una constante (+1) en este caso. Esto da una cota asintótica inferior para${\displaystyle T(n)}$, que en notación de Landau se da como${\displaystyle \Omega \left(n^{\log _{2}(n)/(2+\epsilon )}\right)}$para cualquier${\displaystyle \epsilon >0}$Por lo tanto, Slowsort no es de tiempo polinomial .