algorithm - Aranging integers in a specific order

Question

Given a set of distinct unsorted integers s1, s2, .., sn how do you arrange integers such that s1 < s2 > s3 < s4...

I know this can be solved by looking at the array from left to right and if the condition is not satisfied swapping those two elements gives the right answer. Can someone explain me why this algorithm works.

Answer 1

Given any three successive numbers in the array, there are four possible relationships:

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

In the first case we know that a < c. Since the first condition is met, we can swap b and c to meet the second condition, and the first condition is still met.

In the second case, both conditions are already met.

In the third case, we have to swap a and b to give b < a ? c. But we already know that b < c, so if a < c then swapping to meet that second condition doesn't invalidate the first condition.

In the last case we know that a > c, so swapping a and b to meet the first condition maintains the validity of the second condition.

Now, you add a fourth number to the sequence. You have:

a < b > c ? d

If c < d then there's no need to change anything. But if we have to swap c and d, the prior condition is still met. Because if b > c and c > d, then we know that b > d. So swapping c and d gives us b > d < c.

You can use similar reasoning when you add the fifth number. You have a < b > c < d ? e. If d > e, then there's no need to change anything. If d < e, then by definition c < e as well, so swapping maintains the prior condition.

Pseudo code that implements the algorithm:

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