{"post":"

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:

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

Code:

#include <iostream>\nusing namespace std;\nvoid getnum(int arr[], int l, int m, int r)\n{\nint i, j, k;\nint n1 = m - l + 1;\nint n2 = r - m;\nint LA[n1], RA[n2];
\nfor (i = 0; i &lt; n1; i++)\n\tLA[i] = arr[l + i];\n\nfor (j = 0; j &lt; n2; j++)\n\tRA[j] = arr[m + 1 + j];\n\ni = 0;\nj = 0;\nk = l;\n\nwhile (i &lt; n1 && j &lt; n2)\n{\n\tif (LA[i] &lt;= RA[j])\n\t{\n\t\tarr[k] = LA[i];\n\t\ti++;\n\t}\n\telse\n\t{\n\t\tarr[k] = RA[j];\n\t\tj++;\n\t}\n\tk++;\n}\n\nwhile (i &lt; n1)\n{\n\tarr[k] = LA[i];\n\ti++;\n\tk++;\n}\n\nwhile (j &lt; n2)\n{\n\tarr[k] = RA[j];\n\tj++;\n\tk++;\n}\n
\n}
\nvoid ms(int arr[], int l, int r)\n{\nif (l < r)\n{\nint m = l + (r - l) / 2;\nms(arr, l, m);\nms(arr, m + 1, r);\ngetnum(arr, l, m, r);\n}\n}
\nvoid zigzag(int arr[], int len)\n{\nint temp;\nif (len % 2 == 0)\n{\nfor (int i = 1; i < len - 1; i += 2)\n{\ntemp = arr[i];\narr[i] = arr[i + 1];\narr[i + 1] = temp;\n}\n}\nelse\n{\nfor (int i = 1; i < len; i += 2)\n{\ntemp = arr[i];\narr[i] = arr[i + 1];\narr[i + 1] = temp;\n}\n}
\nfor (int i = 0; i &lt; len; i++)\n{\n\tcout &lt;&lt; arr[i] &lt;&lt; \" \";\n}\n
\n}
\nint main()\n{\nint arr[] = { 1, 5, 2, 3, 7, 6, 4, 8 };\nint len = 8;\nfor (int i = 0; i < len; i++)\n{\ncout << arr[i] << \" \"\n}
\ncout &lt;&lt; endl &lt;&lt; \"After zigzag: \" &lt;&lt; endl;\nms(arr, 0, len - 1);\nzigzag(arr, len);\nreturn 0;\n
\n}

Output:

1 5 2 3 7 6 4 8\nAfter zigzag: \n

1 3 2 5 4 7 6 8

Time Complexity : O(NlogN)

# Optimized Approach

Algorithm:

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.
Iterate through the array elements and initialize a Boolean variable with true.
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(<).
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 (>).
Finally, print the zigzag representation of the array to the console.

Code:

#include <iostream>\nusing namespace std;
\nvoid zigzag(int arr[],int len)
\n{
\n    bool f = true; 
\n    for (int i=0; i<len-1; i++) 
\n    { 
\n        if (f) 
\n        {
\n            if (arr[i] > arr[i+1]) 
\n                swap(arr[i], arr[i+1]); 
\n        } 
\n        else 
\n        { 
\n            if (arr[i] < arr[i+1]) 
\n                swap(arr[i], arr[i+1]); 
\n        } 
\n        f = !(f);
\n    } 
\n  for(int i=0;i<len;i++)
\n   {
\n        cout<<arr[i]<<\" \";
\n   }
\n}
\nint main()
\n{
\n    int arr[]={1,5,2,3,7,6,4,8};  
\n    int len=8;
\n    for(int i=0;i<len;i++)
\n    {
\n      cout<<arr[i]<<\" \";
\n    }
\n    cout<<endl<<\"After zigzag:\"<<endl;
\n    zigzag(arr,len);
\n    return 0;
\n}

Output:

1 5 2 3 7 6 4 8\nAfter zigzag: \n

1 5 2 7 3 6 4 8

Time Complexity: O(N)

This way we can enhance our code for improving efficiency.

\n","title":"Zig zag pattern in C++","authorDetails":{"name":"Ankita Khan","slug":"ankita-khan"},"seo":{"title":"Zig zag pattern in C++"},"description":"The input contains an unsorted array with multiple elements in it. The output is the array representation in a zigzag fashion.","slug":"Convert-the-array-in-zig-zag-fashion-Problem/","articleId":"636a83447bb1ce5072622b7c","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}