Перегруппировать / отсортировать список по величине, наименьшему, второму по величине, второму наименьшему и т. Д.

Question

Учитывая массив целых чисел, как я могу отсортировать их по: наибольшему-наименьшему-2-му по величине - 2-му наименьшему?

Я пытаюсь: - Дублировать и сортировать массив в порядке возрастания и убывания -Создайте отсортированный массив, выбирая заголовок каждого массива, как описано выше

Я не знаком с программированием на Haskell, но вот что я сделал

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)

Заранее спасибо за вашу помощь

Answer 1

frontEndSort использует список xs, сортирует элементы в порядке убывания.Затем выполните сопряжение каждого элемента в xs с элементом из того же списка, но в порядке возрастания.Преобразуйте каждую пару в список, а затем сведите весь список.Наконец, мы берем столько элементов, сколько в xs.

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

Answer 2

Еще один способ использования архивирования:

import Data.Ord

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

Здесь traverse ZipList :: [[b]] -> ZipList [b], поэтому он уже создает пары в виде списков, а не кортежей.

Answer 3

braid функция объединяет два элемента списка на элемент.Затем мы применяем braid к списку, упорядоченному по возрастанию и убыванию.Наконец, поскольку мы в итоге дублируем оригинальный список, мы берем только длину исходного списка.

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

Сравнительный тест:

, несмотря на тот факт, что я думаю, что моя реализацияДля начинающих на Haskell легче понять, что после того, как я проверил свое решение по отношению к решению ƛƛƛ, мое решение примерно в 4-7 раз медленнее, чем его / ее.

Для списка из ста тысяч:

• моя: 211 мс
• :: 53 мс

Для списка длиной в миллион:

• моя: 3,8 с
• ƛƛƛ: 547 мс

Редактировать два: Не использовать reverse

Замена desc = reverse asc на desc = sortOn Down xs создает ту же программу скорости, что и для аппликативного решения and иреализация списка понимания волеизъявления.