CODEWITHSUNDEEP
algorithmlanguage-agnostic
mousey
mousey

Reputation: 11901

Aranging integers in a specific order

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.

Upvotes: 2

Views: 833

Answers (2)

aaronman
aaronman

Reputation: 18751

Here is the code to the suggested solution in java. 

public static int [] alternatingList(int [] list) {
    int first, second,third;
    for (int i = 0;i < list.length-2;i+=2) {
        first = list[i];
        second = list[i+1];
        third = list[i+2];
        if (first > second && first > third) {
            list[i+1] = first;
            list[i] = second;
        }
        else if (third> first && third > second) {
            list[i+1] = third;
            list[i+2] = second;
        }
    }
    return list;
}

In this code since all the numbers are distinct there will always be a bigger number to put into the "peaks". Swapping the numbers will not change the consistency of the last part you did because the number you swap out will always be smaller than the one you put into the new peak.

Keep in mind this code doesn't handle some edge cases like even length lists and lists smaller than three, I wrote it pretty fast :), I only wrote the code to illustrate the concept of the solution

In addition this solution is better than the one in the proposed dupe because it makes one pass. The solution in the dupe uses the hoare's selection algorithm which is n but requires multiple decreasing in size passes on the list, also it needs to make another n pass on the list after using Hoare's (or the median of medians).

More mathematical proof:
For every three consecutive numbers a,b,c there are three options

a > b && a > c
b > c && b > a
c > a && c > b

In the first case you switch a into the middle because it's the largest, second case do nothing (largest is already in the middle) and 3rd case 'c` goes to the middle.

now you have a < b > c d e where for now d and e are unknown. Now the new a,b,c are c,d,e and you do the same operation this is guaranteed not to mess up the order since c will only be changed if it is larger than d and e thus the number moved into c's spot will be smaller than b and not break the ordering, this can continue infinitely clearly with the order never breaking.

Upvotes: 1

Jim Mischel
Jim Mischel

Reputation: 134045

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

Upvotes: 8

Related Questions