2

並べ替えられていない一連の個別の整数 s1、s2、..、sn が与えられた場合、s1 < s2 > s3 < s4... となるように整数をどのように配置しますか?

これは、配列を左から右に見て解決できることを知っています。条件が満たされない場合、これらの 2 つの要素を交換すると正しい答えが得られます。このアルゴリズムが機能する理由を誰かが説明してくれますか?

4

2 に答える 2

8

配列内の任意の 3 つの連続する数値を指定すると、次の 4 つの関係が考えられます。

a < b < c
a < b > c
a > b < c
a > b > c

最初のケースでは、a < c であることがわかっています。最初の条件が満たされているので、b と c を交換して 2 番目の条件を満たすことができ、最初の条件は引き続き満たされます。

2 番目のケースでは、両方の条件がすでに満たされています。

3 番目のケースでは、a と b を交換して b < a ? を与える必要があります。c. しかし、b < c であることは既にわかっているので、a < c の場合、その 2 番目の条件を満たすためにスワップしても、最初の条件が無効になることはありません。

最後のケースでは、a > c であることがわかっているため、最初の条件を満たすために a と b を交換すると、2 番目の条件の有効性が維持されます。

ここで、シーケンスに 4 番目の数値を追加します。あなたが持っている：

a < b > c ? d

c < d の場合、何も変更する必要はありません。ただし、c と d を交換する必要がある場合でも、前の条件は満たされます。b > c かつ c > d の場合、b > d であることがわかるからです。したがって、c と d を入れ替えると、b > d < c となります。

5 番目の数値を追加する場合も、同様の推論を使用できます。あなたが持っていa < b > c < d ? eます。d > e の場合、何も変更する必要はありません。d < e の場合、定義により c < e であるため、スワッピングは前の状態を維持します。

アルゴリズムを実装する疑似コード:

for i = 0 to n-2
    if i is even
        if (a[i] > a[i+1])
            swap(a[i], a[i+1])
        end if
    else
        if (a[i] < a[i+1])
            swap(a[i], a[i+1])
    end
于 2013-07-21T23:19:06.490 に答える