Haskell Language
Sorteeralgoritmen
Zoeken…
Invoegsortering
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)
Voorbeeld gebruik:
> isort [5,4,3,2,1]
Resultaat:
[1,2,3,4,5]
Sorteren samenvoegen
Geordende samenvoeging van twee geordende lijsten
Duplicaten bewaren:
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
Top-down versie:
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
Het is op deze manier gedefinieerd voor duidelijkheid, niet voor efficiëntie.
Voorbeeld gebruik:
> msort [3,1,4,5,2]
Resultaat:
[1,2,3,4,5]
Bottom-up versie:
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
Snel sorteren
qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort [a | a <- xs, a < x]
++ [x] ++
qsort [b | b <- xs, b >= x]
Bellen soort
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
Permutatie Sorteren
Ook bekend als 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
Zeer inefficiënt (op de computers van vandaag).
Selectie sorteren
Selectie sorteren selecteert het minimale element herhaaldelijk totdat de lijst leeg is.
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
Licentie onder CC BY-SA 3.0
Niet aangesloten bij Stack Overflow