Haskell Language
Clasificación de los algoritmos
Buscar..
Tipo de inserción
insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys) | x < y = x:y:ys
| otherwise = y:(insert x ys)
isort :: Ord a => [a] -> [a]
isort [] = []
isort (x:xs) = insert x (isort xs)
Ejemplo de uso:
> isort [5,4,3,2,1]
Resultado:
[1,2,3,4,5]
Combinar clasificación
Fusión ordenada de dos listas ordenadas.
Preservando los duplicados:
merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) | x <= y = x:merge xs (y:ys)
| otherwise = y:merge (x:xs) ys
Versión de arriba abajo:
msort :: Ord a => [a] -> [a]
msort [] = []
msort [a] = [a]
msort xs = merge (msort (firstHalf xs)) (msort (secondHalf xs))
firstHalf xs = let { n = length xs } in take (div n 2) xs
secondHalf xs = let { n = length xs } in drop (div n 2) xs
Se define de esta manera por claridad, no por eficiencia.
Ejemplo de uso:
> msort [3,1,4,5,2]
Resultado:
[1,2,3,4,5]
Versión de abajo hacia arriba:
msort [] = []
msort xs = go [[x] | x <- xs]
where
go [a] = a
go xs = go (pairs xs)
pairs (a:b:t) = merge a b : pairs t
pairs t = t
Ordenación rápida
qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort [a | a <- xs, a < x]
++ [x] ++
qsort [b | b <- xs, b >= x]
Ordenamiento de burbuja
bsort :: Ord a => [a] -> [a]
bsort s = case bsort' s of
t | t == s -> t
| otherwise -> bsort t
where bsort' (x:x2:xs) | x > x2 = x2:(bsort' (x:xs))
| otherwise = x:(bsort' (x2:xs))
bsort' s = s
Orden de permutación
También conocido como bogosort .
import Data.List (permutations)
sorted :: Ord a => [a] -> Bool
sorted (x:y:xs) = x <= y && sorted (y:xs)
sorted _ = True
psort :: Ord a => [a] -> [a]
psort = head . filter sorted . permutations
Extremadamente ineficiente (en las computadoras de hoy).
Selección de selección
La selección de selección selecciona el elemento mínimo, repetidamente, hasta que la lista esté vacía.
import Data.List (minimum, delete)
ssort :: Ord t => [t] -> [t]
ssort [] = []
ssort xs = let { x = minimum xs }
in x : ssort (delete x xs)
Modified text is an extract of the original Stack Overflow Documentation
Licenciado bajo CC BY-SA 3.0
No afiliado a Stack Overflow