algorithm - Aranging integers in a specific order -

given set of distinct unsorted integers s1, s2, .., sn how arrange integers such s1 < s2 > s3 < s4...

i know can solved looking @ array left right , if condition not satisfied swapping 2 elements gives right answer. can explain me why algorithm works.

given 3 successive numbers in array, there 4 possible relationships:

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

in first case know < c. since first condition met, can swap b , c meet second condition, , first condition still met.

in second case, both conditions met.

in third case, have swap , b give b < ? c. know b < c, if < c swapping meet second condition doesn't invalidate first condition.

in last case know > c, swapping , b meet first condition maintains validity of second condition.

now, add fourth number sequence. have:

a < b > c ? d 

if c < d there's no need change anything. if have swap c , d, prior condition still met. because if b > c , c > d, know b > d. swapping c , d gives b > d < c.

you can use similar reasoning when add fifth number. have a < b > c < d ? e. if d > e, there's no need change anything. if d < e, definition c < e well, swapping maintains prior condition.

pseudo code implements algorithm:

for = 0 n-2     if         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