Convert array into Zig-Zag fashion

Given an array Arr (distinct elements) of size N. Rearrange the elements of array in zig-zag fashion. The converted array should be in form a < b > c < d > e < f. The relative order of elements is same in the output i.e you have to iterate on the original array only.

• Time : O(n)
• Space : O(1)

class Solution{
public:
    // Program for zig-zag conversion of array
    void zigZag(int arr[], int n) {
        for(int i = 0, j = 1; i < n - 1; i++,j++) {
            if(arr[i] > arr[j] and !(i & 1)) swap(arr[i], arr[j]);
            else if(arr[i] < arr[j] and (i & 1)) swap(arr[i], arr[j]);
        }
    }
};