Clasificación lenta
Slowsort es un algoritmo de clasificación poco práctico y gracioso . Se basa en el principio multiplica y ríndete (ing. multiplica y ríndete ), una parodia de divide y vencerás . Fue publicado por Andrey Broder y Jorge Stolfi en 1986 en su artículo Pessimal Algorithms and Simplexity Analysis [1] ( Algoritmos pessimales y análisis de simplicidad , una parodia de algoritmos óptimos y análisis de complejidad ).
Algoritmo
La ordenación lenta es un algoritmo recursivo . En pseudocódigo , se implementa de la siguiente manera:
Subrutina slowsort(A,i,j) // ordena el Array A[i], ..., A[j] si i >= j entonces regresa m := ⌊(i+j)/2⌋ clasificación lenta(A,i,m) // (1.1) ordenación lenta(A,m+1,j) // (1.2) si A[j] < A[m] entonces intercambia A[j] y A[m] // (1.3) clasificación lenta(A,i,j-1) // (2)- Ordenar recursivamente la primera mitad (1.1);
- Ordenar recursivamente la segunda mitad (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 matriz (1.3);
- Ordenar recursivamente todo el arreglo excepto el máximo.
Posible implementación en Haskell :
clasificación lenta :: Ord a => [a] -> [a] clasificación lenta xs | longitud xs <= 1 = xs | de lo contrario = ordenación lenta xsnew ++ [max llast rlast] -- (2) dónde l = clasificación lenta $ tomar m xs -- (1.1) r = clasificación lenta $ soltar m xs -- (1.2) último = último l rlast = última r xsnew = init l ++ min llast rlast : init r m = fst(divMod(longitud xs) 2)Dificultad
El tiempo de ejecución de un género lento es . La ordenación lenta no está en tiempo polinomial . Incluso en el mejor de los casos, es peor que el tipo burbuja .
Fuentes
- ↑ CiteSeerX: algoritmos pesimales y análisis de simplexidad . Citeseerx.ist.psu.edu . Consultado el 26 de julio de 2017. Archivado desde el original el 30 de enero de 2017.
| 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 | |