C++ program to convert an array into Zig-Zag fashion

In this article, we will learn how to convert an array into zig-zag fashion in C++. Let’s consider an array arr with elements {a, b, c, d, e, f, g} the array is said to bein zig zag form when a<b>c<d>e<f>g.

Zig-Zag Fashion array in C++

Method 1: Sorting array

1. Firstly sort the given array using sort() fucntion.

2.Iterate the array from range 1 to n-1

  • Now swap(arr[i], arr[i+1])

4. Finally, print the array.

#include <bits/stdc++.h>
using namespace std;

void zigZagArray(int arr[], int n){
    sort(arr, arr+n);
    int temp;
    for(int i=1;i<n-1;i=i+2){
        temp = arr[i];
        arr[i] = arr[i+1];
        arr[i+1] = temp;
    }
}
int main(){
    int arr[] = {3, 2, 1, 7, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    zigZagArray(arr, n);
    cout<<"Zig-Zag form of the given array is"<<endl;
    for(int i =0;i<n;i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}

Output

Zig-Zag form of the given array is
1 3 2 9 7

Time Complexity: O(nlogn) where n is the size of the array

Space Complexity: O(1)

Method 2:

1. Firstly, declare a boolean flag represents what operation(‘<‘ or ‘>’) we need to use right now.

2. Iterate the array from the range o to n-2

  • If flag is true and (arr[i]>arr[i+1]) then swap( arr[i], arr[i+1]).
  • If flag is false and (arr[i]<arr[i+1]) then swap (arr[i], arr[i+1]).

3. Finally, print the array.

#include<bits/stdc++.h>
using namespace std;

// function to convert given array in zig zag fashion
void zigZagArray(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[] = {3, 12, 4, 2, 0, 1, -1};
    int n = sizeof(arr)/sizeof(arr[0]);
    zigZagArray(arr, n);
    cout<<"Zig-Zag form of the given array is"<<endl;
    for(int i =0;i<n;i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}

Output

Zig-Zag form of the given array is
3 12 2 4 0 1 -1

Time complexity: O(n) where n is size of the array.

Space complexity: O(1)

Also, read

Leave a Reply

Your email address will not be published. Required fields are marked *