Clasificación lenta - Slowsort
Slowsort es un algoritmo de clasificación . Es de naturaleza humorística y no es útil. Es un algoritmo reacio basado en el principio de multiplicar y rendirse (una parodia formada tomando los opuestos de divide y vencerás ). Fue publicado en 1986 por Andrei Broder y Jorge Stolfi en su artículo Pessimal Algorithms and Simplexity Analysis (una parodia de algoritmos óptimos y análisis de complejidad ).
Algoritmo
Slowsort es un algoritmo recursivo .
- Ordena en el lugar .
- Es un tipo estable . (No cambia el orden de las claves de igual valor).
Esta es una implementación en pseudocódigo:
procedure slowsort(A[], i, j) // Sort array range A[i ... j] in-place.
if i ≥ j then
return
m := floor( (i+j)/2 )
slowsort(A, i, m) // (1.1)
slowsort(A, m+1, j) // (1.2)
if A[j] < A[m] then
swap A[j] , A[m] // (1.3)
slowsort(A, i, j-1) // (2)
- Ordene la primera mitad, de forma recursiva. (1,1)
- Ordene la segunda mitad, de forma recursiva. (1,2)
- Encuentre el máximo de toda la matriz comparando los resultados de 1.1 y 1.2, y colóquelo al final de la lista. (1,3)
- Ordene la lista completa (excepto el máximo ahora al final), de forma recursiva. (2)
Una implementación no optimizada en Haskell (puramente funcional) puede tener el siguiente aspecto:
slowsort :: (Ord a) => [a] -> [a]
slowsort xs
| length xs <= 1 = xs
| otherwise = slowsort xs' ++ [max llast rlast] -- (2)
where 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
Complejidad
El tiempo de ejecución de Slowsort es .
Un límite asintótico inferior para en la notación de Landau es para any .
Por lo tanto, la ordenación lenta no está en tiempo polinomial . Incluso el mejor de los casos es peor que el tipo de burbuja .