Recent Posts

Zig zag pattern in C++

Written by

Ankita Khan

Convert the array in zig-zag fashion Problem

Input: arr = {1,3,5,7,9,2,4}; 

Output: {1,3,2,5,4,9,7}

Explanation: The input contains an unsorted array with multiple elements in it. The output is the array representation in a zigzag fashion. There can be multiple outputs of this problem. One just has to maintain the pattern a<b>c<d>e<f.

There are two approaches to solve it:

Case 1: Sort the array in ascending order and interchange the positions of 2nd and 3rd element, 4th and 5th element, 6th and 7th element and so on.

Case 2: Using a single loop to iterate through elements and maintain a flag to check > or < for each alternate positions.

# Brute Force

Algorithm:

  1. Pass the given array to the sort the array using the merge sort technique.
  2. The function zigzag rearranges the sorted array in a zigzag fashion.
  3. Print the result on the screen.

Code:

#include <iostream>
using namespace std;

void getnum(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int LA[n1], RA[n2];


for (i = 0; i &lt; n1; i++)
	LA[i] = arr[l + i];

for (j = 0; j &lt; n2; j++)
	RA[j] = arr[m + 1 + j];

i = 0;
j = 0;
k = l;

while (i &lt; n1 &amp;&amp; j &lt; n2)
{
	if (LA[i] &lt;= RA[j])
	{
		arr[k] = LA[i];
		i++;
	}
	else
	{
		arr[k] = RA[j];
		j++;
	}
	k++;
}

while (i &lt; n1)
{
	arr[k] = LA[i];
	i++;
	k++;
}

while (j &lt; n2)
{
	arr[k] = RA[j];
	j++;
	k++;
}



}


void ms(int arr[], int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
ms(arr, l, m);
ms(arr, m + 1, r);
getnum(arr, l, m, r);
}
}


void zigzag(int arr[], int len)
{
int temp;
if (len % 2 == 0)
{
for (int i = 1; i < len - 1; i += 2)
{
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
else
{
for (int i = 1; i < len; i += 2)
{
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}


for (int i = 0; i &lt; len; i++)
{
	cout &lt;&lt; arr[i] &lt;&lt; " ";
}



}


int main()
{
int arr[] = { 1, 5, 2, 3, 7, 6, 4, 8 };
int len = 8;
for (int i = 0; i < len; i++)
{
cout << arr[i] << " "
}


cout &lt;&lt; endl &lt;&lt; "After zigzag: " &lt;&lt; endl;
ms(arr, 0, len - 1);
zigzag(arr, len);
return 0;



}

Output:

1 5 2 3 7 6 4 8

After zigzag:


1 3 2 5 4 7 6 8

Time Complexity : O(NlogN)

# Optimized Approach

Algorithm:

  1. Pass the array with its length to convert it in zigzag fashion that is, a<b>c<d>e<f>g<h… and so on.
  2. Iterate through the array elements and initialize a Boolean variable with true.
  3. If the current array element is greater than the next array element and if the bool variable is true, swap both the array elements as the expected relation is less than(<).
  4. If the current array element is smaller than the next array element and if the bool variable is false, swap both the array elements as the expected relation is greater than (>).
  5. Finally, print the zigzag representation of the array to the console.

Code:

#include <iostream>

using namespace std;


void zigzag(int arr[],int len)


{


    bool f = true; 


    for (int i=0; i<len-1; i++) 


    { 


        if (f) 


        {


            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]); 


        } 


        f = !(f);


    } 


  for(int i=0;i<len;i++)


   {


        cout<<arr[i]<<" ";


   }


}


int main()


{


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


    int len=8;


    for(int i=0;i<len;i++)


    {


      cout<<arr[i]<<" ";


    }


    cout<<endl<<"After zigzag:"<<endl;


    zigzag(arr,len);


    return 0;


}

Output:

1 5 2 3 7 6 4 8

After zigzag:


1 5 2 7 3 6 4 8

Time Complexity: O(N)

This way we can enhance our code for improving efficiency.

Zig zag pattern in C++