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