How to infer permutation B so that A is wiggly?

Question

I came across the following question:

Given an unsorted array of B[1 . . 2n+1]real numbers, give a linear one that produces a permutation A[1..2n+1]of of Bsuch that it Ais wiggly.

I basically did a merge sort and changed it:

 MergeSort(a,n)
      int i=2;
     while (i ≤ n)
     {
       Swap(a[i−1], a[i]);
       i=i+2;
     }

But the time complexity O(nlogn) + O(n)(from sorting and from loop, respectively) that gives O(nlogn). But I want to do it in O(n)time.

Should I use sorting sorting / sorting sorting / sorting notation to get linear time and then change it to get a wiggly array?

Answer 1

:

for i = 2 ... 2 * n - 1:
     if i % 2 == 0 and a[i] < a[i - 1] or i % 2 == 1 and a[i] > a[i - 1]:
         swap(a[i], a[i - 1])

:

:

• : , .

• : if i % 2 == 0: - , . : a[i - 2] >= a[i - 1] > a[i]. , , i - 2 i - 1, . i .

Answer 2

++ .

 #include <iostream>
using namespace std;

void swap(int& a,int& b){
a=a+b;
b=a-b;
a=a-b;
}

int main() {
    int*B ;
    int n;
    cin>>n ; n=2*n;
    B=new int[n] ;
    for(int i=0;i<n;i++){
        cin>>B[i] ;
    }

    for(int i=1;i<n;i++){
        if(i%2==0&&B[i]>B[i-1])
            swap(B[i],B[i-1]);
            else if(i%2==1&&B[i]<B[i-1])
            swap(B[i],B[i-1]);


    }

    for(int i=0;i<n;i++){
        cout<<B[i]<<" ";
    }
    return 0;
}