CODEWITHSUNDEEP
listsortinghaskell
Cleola
Cleola

Reputation: 23

Rearrange/sort list by largest, smallest, second largest, second smallest etc

Given an array of integers, how can I sort them by : largest-smallest-2nd largest - 2nd smallest?

I'm trying to : - Duplicate and sort an array in order ascending and descending - Create the sorted array by picking the head of each arrays describes as above

I am not familiar with Haskell programming but here's what I've done

sort :: [Int] -> [Int]
sort [] = []
sort (x:xs) = sort smaller ++ [x] ++ sort larger
  where
    smaller = filter (<= x) xs
    larger = filter (> x) xs

wave :: [Int] -> [Int]
wave [] = []
wave [x] = [x]
wave (x:xs) = if length (x:xs)>1 
    then :
        ascending = sort (x:xs)
        descending = reverse (ascending)
        iterator = length(x:xs)
        if iterator > 0 && (length(ascending)==0 || length(descending)==0)
            then do wave(x:xs) = head(descending) + head(ascending)
                tail(descending)
                tail(ascending)

Thanks by advance for your help

Upvotes: 1

Views: 1122

Answers (3)

Will Ness
Will Ness

Reputation: 71065

Another way to use the zipping:

import Data.Ord

frontEndSort :: [Int] -> [Int] 
frontEndSort xs =
    zipWith (flip const) xs
       ( concat . getZipList . traverse ZipList
                $ [sortBy (comparing Down) xs, sort xs] )

Here traverse ZipList :: [[b]] -> ZipList [b] so it already produces the pairs as lists, not tuples.

Upvotes: 1

lsmor
lsmor

Reputation: 5063

braid function intercalates two list elem by elem. We next apply braid to the list ordered in ascending and descending. Finally, since we end up with the orginal list duplicated, we take just the length of the original list.

braid :: [Int] -> [Int] -> [Int]    
braid []     as     = as
braid ds     []     = ds
braid (d:ds) (a:as) = d:a:braid ds as

wave :: [Int] -> [Int]
wave xs = take (length xs) braided 
  where asc  = sort xs
        desc = reverse asc
        braided = braid desc asc

Benchmark Edit:

despite of the fact that I think my implementation is easier to understand for haskell beginers, I got to say that after having benckmarked my solution against ƛƛƛ's solution, mine is ~ 4 to 7 times slower than his/her.

For One hundred thousand length list:

  • mine: 211 ms
  • ƛƛƛ's: 53 ms

For One million length list:

  • mine: 3.8 sec
  • ƛƛƛ's: 547 ms

Edit Two: Don't use reverse

Replacing desc = reverse asc by desc = sortOn Down xs produces same speed program as ƛƛƛ's applicative solution and willness comprehension list implementation.

Upvotes: 1

ƛƛƛ
ƛƛƛ

Reputation: 892

frontEndSort consumes a list xs, it sorts its elements in descending order. Next, pair each element in xs with element from the same list but in ascending order. Convert each pair to a list then flatten the whole list. Finally, we take as many elements as in xs.

frontEndSort :: [Int] -> [Int] 
frontEndSort xs = take (length xs) $ do
    (x, y) <- zip <$> sortBy (comparing Down) <*> sort $ xs
    [x, y]

Upvotes: 4

Related Questions