arrays - 各要素が隣接する要素よりも大きい/小さいように配列を再配置する方法

Question

たとえば、数値が次の場合:

30, 12, 49, 6, 10, 50, 13

配列は次のようになります。

[10, 6, 30, 12, 49, 13, 50]

ご覧のように：

• 6 は 10 と 30 の両方より小さく、
• 49 は 12 や 13 などよりも大きくなります。

数字はすべて異なり、本物です。最も効率的なアルゴリズムが必要です。

Answer 1

数値がすべて異なると仮定すると、おそらく最も簡単な方法は、数値を並べ替えてから、並べ替えられたリストの前半と後半をインターリーブすることです。これにより、必要な高/低/高/低/高/低/....パターンが保証されます。

このアルゴリズムはO(n log n)、ほとんどの目的で十分に効率的であり、標準ライブラリの最適化された並べ替えルーチンの恩恵を受ける可能性があります。

数値が明確でない場合、解がない可能性があります (たとえば、数値がすべて等しい場合)。

Answer 2

私は複雑さについてあまり詳しくありませんが、これが私の考えです。

For even length lists:

(For our odd length example, 
 put 30 aside to make the list even) 

1. Split the list into chunks of 2    => [[12,49],[6,10],[50,13]]
2. Sort each chunk                    => [[12,49],[6,10],[13,50]]
3. Reverse-sort the chunks by 
   comparing the last element of 
   one to the first element of 
   the second                         => [[12,49],[13,50],[6,10]]

For odd length lists:
4. Place the removed first element in 
   the first appropriate position     => [30,12,49,13,50,6,10]

Haskell コード:

import Data.List (sortBy)
import Data.List.Split (chunksOf)

rearrange :: [Int] -> [Int]
rearrange xs
  | even (length xs) = rearrangeEven xs
  | null (drop 1 xs) = xs
  | otherwise        = place (head xs) (rearrangeEven (tail xs))
 where place x (y1:y2:ys) 
         | (x < y1 && y1 > y2) || (x > y1 && y1 < y2) = (x:y1:y2:ys)
         | otherwise                                  = place' x (y1:y2:ys)
       place' x (y1:y2:ys) 
         | (x < y1 && x < y2) || (x > y1 && x > y2) = (y1:x:y2:ys)
         | otherwise                                = y1 : (place' x (y2:ys))
       rearrangeEven = concat 
                     . sortBy (\a b -> compare (head b) (last a)) 
                     . map sort
                     . chunksOf 2

出力：

*Main> rearrange [30,12,49,6,10,50,13]
[30,12,49,13,50,6,10]

*Main> rearrange [1,2,3,4]
[3,4,1,2]