Convert array into Zig-Zag fashion

Problem Statement

The problem “Convert array into Zig-Zag fashion” states that you are given an – of integers. The problem statement asks to sort the array in a zig-zag manner such that the elements in the array will look like à  a < b > c < d > e < f.

Example

arr[] = {2,4,5,1,7,6,8}

[2, 5, 1, 7, 4, 8, 6]

Explanation

5 is greater than both 1 and 2(its adjacent elements),  7 is greater than both its adjacent elements, so is 8.

Algorithm

1. Mark flag is equal to true.
2. Traverse the array from 0 to n-2, where n is the length of the array.
  1. Check if the flag is true
    1. Check if the current element is greater than the next element.
      1. Swap those values.
    2. Else, check if the current element is greater than the next element,
      1. Check if the current element is lesser than the next element.
        1. Swap those values.
3. Flip the value of the flag.

Explanation

We have given an array of integers. Our task is to rearrange the array into a zigzag manner. We have given a condition such that even number elements should be greater than its two adjacent elements, in a manner of ‘a < b > c < d > e < f’. We can see here that b and d are greater than its two adjacent elements, ‘a’ and ‘c’ are lesser than its two adjacent elements. Our task is to arrange the given array like this. For this, we are going to swap the values, while traversing the array, such that is arranged in a zigzag manner.

We will be marked one Boolean value to true, then we are going to start traversing the loop, and check if the flag is true, or not. If it is true, then we will check for the current value if the current value is greater than its next value. Then we are going to swap those values. And mark the Boolean values to false. We just have to revert its value, if it is true, then update it to false, if it is false, update it to true. So with every alternative traversal, for every iteration there will be the different flag values. So with this, only a part is going to be executed, either if part or else part.

The same thing we will be done with the else part, to swap the values. If the current value of array in a traversal is less than the next value. And after the traversal, we just have to print the array in which we have made updations.

Code

C++ code to Convert array into Zig-Zag fashion

#include <iostream>

using namespace std;

void sortZigZag(int arr[], int n)
{
    bool flag = true;

    for (int i=0; i<=n-2; i++)
    {
        if (flag)
        {
            if (arr[i] > arr[i+1])
                swap(arr[i], arr[i+1]);
        }
        else
        {
            if (arr[i] < arr[i+1])
                swap(arr[i], arr[i+1]);
        }
        flag = !flag;
    }
}
int main()
{
    int arr[] = {2,4,5,1,7,6,8};
    int n = sizeof(arr)/sizeof(arr[0]);
    sortZigZag(arr, n);
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
    return 0;
}

2 5 1 7 4 8 6

Java code to Convert array into Zig-Zag fashion

import java.util.Arrays;

class zigzagArray
{
    public static void sortZigZag(int arr[])
    {
        boolean flag = true;

        int temp =0;

        for (int i=0; i<=arr.length-2; i++)
        {
            if (flag)
            {
                if (arr[i] > arr[i+1])
                {
                    temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }

            }
            else
            {
                if (arr[i] < arr[i+1])
                {
                    temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
            if(flag==true)
                flag=false;
            else
                flag=true;
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {2,4,5,1,7,6,8};
        sortZigZag(arr);
        System.out.println(Arrays.toString(arr));
    }
}

[2, 5, 1, 7, 4, 8, 6]

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Since we have just traversed over the elements in the array. The time complexity is linear.

Space Complexity

O(1) as no extra space is required. Since we have not used any extra space, the space complexity is constant.