Rosetta Code

Sorting Algorithms/Circle Sort: Difference between revisions

Page Discussion

Sorting Algorithms/Circle Sort (view source)

Revision as of 17:03, 28 July 2020

93 bytes removed ,  3 years ago
→‎{{header|Haskell}}: Updated Haskell code
(added Haskell implementation)
(→‎{{header|Haskell}}: Updated Haskell code)
Line 985:
It also uses the Writer monad to track whether or not there have been swaps.
 
<lang haskell>dataimport SwappedData.Monoid = NoSwaps | Swapped(Any(..))
import Data.Bool (bool)
 
instance Semigroup Swapped where
Swapped <> _ = Swapped
NoSwaps <> y = y
 
instance Monoid Swapped where
mempty = NoSwaps
 
circleSort :: Ord a => [a] -> [a]
circleSort xs = gotif swapped then circleSort (ks []) else ks []
where
got xs(Any swapped,ks) = casego gokFalse xs of
(NoSwaps,ys) -> ys []
(Swapped,ys) -> got (ys [])
 
gok [] = pure id
gok [x] = pure ((:) x)
gok xs = do
(_,ls,rs) <- go xs xs▼
(.) <$> gok ls <*> gok (reverse rs)
go (y:ys)d (_:_:zs)[] = f y =<< go yspure zsid
go ys d [x] = =pure (NoSwaps,(ys,[],[]:) x)
go (y:ys)d [_]xs = do
| y(_,ls,rs) <=- headhalve ysd xs = (NoSwaps,(ys,[y],[]))xs
|(.) otherwise<$> go False ls <*> go =True (Swapped,(ys,[],[y]))rs
 
fhalve xd (y:ys,ls,rs) (_:_:zs) = f d y =<< halve d ys zs
halve d |ys [] x <= y = (NoSwaps,pure (ys,x:ls[],y:rs)[])
halve d (y:ys) [_] | otherwise = (Swapped,pure (ys,[y:ls | s],x:rs)[y | not s])
where s = y <= head ys
</lang>
▲ f d x (_y:ys,ls,rs) <- go xs xs
| bool (<=) (<) d x y = (Any d ,(ys,x:ls,y:rs))
| otherwise = (Any (not d),(ys,y:ls,x:rs))</lang>
 
{{out}}
Line 1,026 ⟶ 1,016:
[-1,0,1,2,3,4,5,6,7,8,11,12,13,14]
</pre>
 
 
=={{header|J}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/253837"