C++ program to convert an array into Zig-Zag fashion
By Abinash ReddyIn 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