Given an array of distinct elements of size N, the task is to rearrange the elements of the array in a zig-zag fashion so that the converted array should be in the below form:
arr[0] < arr[1] > arr[2] < arr[3] > arr[4] < . . . . arr[n-2] < arr[n-1] > arr[n].
Examples:
Input: N = 7 , arr[] = {4, 3, 7, 8, 6, 2, 1}
Output: arr[] = {3, 7, 4, 8, 2, 6, 1}
Explanation: The given array is in zig-zag pattern as we can see 3 < 7 > 4 < 8 > 2 < 6 >1Input: N = 4 , arr[] = {1, 4, 3, 2}
Output: arr[] = {1, 4, 2, 3}
Explanation: The given array is in zig-zag pattern as we can see 1 < 4 > 2 < 3
Convert array into Zig-Zag fashion Using Sorting
The Idea is to first sort the array.
After sorting, exclude the first element, swap the remaining elements in pairs. (i.e. keep arr[0] as it is, swap arr[1] and arr[2], swap arr[3] and arr[4], and so on).
Follow the steps mentioned below to implement the idea:
- Sort the array.
- Traverse the array from index 1 to N-1, and increase the value of index by 2.
- While traversing the array swap arr[i] with arr[i+1].
- Print the final array.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void zigZag(vector<int>& arr, int N)
{
// sort the array by using the sort function
sort(arr.begin(), arr.end());
// traverse the array from 1 to N -1
for (int i = 1; i < N - 1; i += 2) {
// swap the current element with the next element
swap(arr[i], arr[i + 1]);
}
// print the complete array
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
}
return;
}
int main()
{
vector<int> arr = { 4, 3, 7, 8, 6, 2, 1 };
int N = 7;
zigZag(arr, N);
return 0;
}
C
#include <stdio.h>
#include <stdlib.h>
int comparator(const void* p, const void* q)
{
return (*(int*)p - *(int*)q);
}
void zigZag(int arr[], int N)
{
// sort the array using the qsort function
qsort((void*)arr, N, sizeof(arr[0]), comparator);
for (int i = 1; i < N - 1; i += 2) {
// swap the value of current element with next
// element
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
// print the complete array
for (int i = 0; i < N; i++)
printf("%d ", arr[i]);
return;
}
int main()
{
int arr[] = { 2, 3, 4, 1, 5, 7, 6 };
int N = 7;
zigZag(arr, N);
return 0;
}
Java
// Java program to sort an array in Zig-Zag form
import java.util.Arrays;
class Test {
static int arr[] = new int[] { 4, 3, 7, 8, 6, 2, 1 };
static void zigZag()
{
// sort the array using the sort function
Arrays.sort(arr);
// traverse the array from 1 to N -1
for (int i = 1; i <= arr.length - 2; i += 2) {
// swap the current element with the next
// element
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
// Driver method to test the above function
public static void main(String[] args)
{
zigZag();
// print the complete array
System.out.println(Arrays.toString(arr));
}
}
Python3
def zigZag(arr, n):
# use sort function to sort the array
arr.sort()
# traverse the array from 1 to n-1
for i in range(1, n-1, 2):
# swap value of current element with next element
arr[i], arr[i+1] = arr[i+1], arr[i]
# print the array
print(arr)
# Driver program
if __name__ == "__main__":
arr = [4, 3, 7, 8, 6, 2, 1]
n = len(arr)
zigZag(arr, n)
C#
// C# program to sort an array in Zig-Zag form
using System;
class GFG {
static int[] arr = new int[] { 4, 3, 7, 8, 6, 2, 1 };
// Method for zig-zag conversion of array
static void zigZag()
{
// sort the array by using the sort function
Array.Sort(arr);
for (int i = 1; i <= arr.Length - 2; i += 2) {
// swap the current element with next next
// element
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
// Driver code
public static void Main(String[] args)
{
zigZag();
// print the array
foreach(int i in arr) Console.Write(i + " ");
}
}
Javascript
<script>
// JavaScript program to sort an array
// in Zig-Zag form
// Program for zig-zag conversion of array
function zigZag(arr, n)
{
// sort the by using the sort function
arr.sort();
//traverse the array from 1 to n-1
for(let i = 1; i <= n - 2; i++)
{
// swap the current element with next element
let temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
// Driver code
let arr = [ 4, 3, 7, 8, 6, 2, 1 ];
let n = arr.length;
zigZag(arr, n);
// print the array
for(let i = 0; i < n; i++)
document.write(arr[i] + " ");
// This code is contributed by Surbhi Tyagi.
</script>
Output
1 3 2 6 4 8 7
Time complexity: O(N*log(N)) because sorting is used.
Auxiliary Space: O(1)
Optimized approach for Convert array into Zig-Zag fashion
In this approach, rather than sorting the complete array, we will maintain a flag for representing which order(i.e.,< or >) we currently need. If the current two elements are not in that order, then swap those elements, otherwise not.
Illustration:
Below is the illustration of above approach.
Follow the steps mentioned below to implement the idea:
- Create a bool variable flag and set it to true
- Traverse the array from index 0 to N-1
- If the value of flag is true then check if arr[i] < arr[i+1] or not , if not then swap
- Flip the value of flag
- If the value of flag is false then check if arr[i] > arr[i+1] or not , if not then swap
- Print the final array.
Below is the implementation of the above approach:
C++
// C++ program to sort an array in Zig-Zag form
#include <iostream>
using namespace std;
// Program for zig-zag conversion of array
void zigZag(int arr[], int n)
{
// Flag true indicates relation "<" is expected,
// else ">" is expected. The first expected relation
// is "<"
bool flag = true;
for (int i = 0; i <= n - 2; i++) {
if (flag) /* "<" relation expected */
{
/* If we have a situation like A > B > C,
we get A > C < B by swapping B and C */
if (arr[i] > arr[i + 1])
swap(arr[i], arr[i + 1]);
}
else /* ">" relation expected */
{
/* If we have a situation like A < B < C,
we get A < C > B by swapping B and C */
if (arr[i] < arr[i + 1])
swap(arr[i], arr[i + 1]);
}
flag = !flag; /* flip flag */
}
}
// Driver program
int main()
{
int arr[] = { 4, 3, 7, 8, 6, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
zigZag(arr, n);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
// This code is contributed by Sania Kumari Gupta
// (kriSania804)
C
// C program to sort an array in Zig-Zag form
#include <stdbool.h>
#include <stdio.h>
// This function swaps values pointed by xp and yp
void swap(int* xp, int* yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// Program for zig-zag conversion of array
void zigZag(int arr[], int n)
{
// Flag true indicates relation "<" is expected,
// else ">" is expected. The first expected relation
// is "<"
bool flag = true;
for (int i = 0; i <= n - 2; i++) {
if (flag) /* "<" relation expected */
{
/* If we have a situation like A > B > C,
we get A > C < B by swapping B and C */
if (arr[i] > arr[i + 1])
swap(&arr[i], &arr[i + 1]);
}
else /* ">" relation expected */
{
/* If we have a situation like A < B < C,
we get A < C > B by swapping B and C */
if (arr[i] < arr[i + 1])
swap(&arr[i], &arr[i + 1]);
}
flag = !flag; /* flip flag */
}
}
// Driver program
int main()
{
int arr[] = { 4, 3, 7, 8, 6, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
zigZag(arr, n);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
// This code is contributed by Sania Kumari Gupta
// (kriSania804)
Java
// Java program to sort an array in Zig-Zag form
import java.util.Arrays;
class Test {
static int arr[] = new int[] { 4, 3, 7, 8, 6, 2, 1 };
// Method for zig-zag conversion of array
static void zigZag()
{
// Flag true indicates relation "<" is expected,
// else ">" is expected. The first expected relation
// is "<"
boolean flag = true;
int temp = 0;
for (int i = 0; i <= arr.length - 2; i++) {
if (flag) /* "<" relation expected */
{
/* If we have a situation like A > B > C,
we get A > C < B by swapping B and C */
if (arr[i] > arr[i + 1]) {
// swap
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
else /* ">" relation expected */
{
/* If we have a situation like A < B < C,
we get A < C > B by swapping B and C */
if (arr[i] < arr[i + 1]) {
// swap
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
flag = !flag; /* flip flag */
}
}
// Driver method to test the above function
public static void main(String[] args)
{
zigZag();
System.out.println(Arrays.toString(arr));
}
}
Python
# Python program to sort an array in Zig-Zag form
# Program for zig-zag conversion of array
def zigZag(arr, n):
# Flag true indicates relation "<" is expected,
# else ">" is expected. The first expected relation
# is "<"
flag = True
for i in range(n-1):
# "<" relation expected
if flag is True:
# If we have a situation like A > B > C,
# we get A > C < B
# by swapping B and C
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
# ">" relation expected
else:
# If we have a situation like A < B < C,
# we get A < C > B
# by swapping B and C
if arr[i] < arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
flag = bool(1 - flag)
print(arr)
# Driver program
arr = [4, 3, 7, 8, 6, 2, 1]
n = len(arr)
zigZag(arr, n)
# This code is contributed by Pratik Chhajer
# This code was improved by Hardik Jain
C#
// C# program to sort an array in Zig-Zag form
using System;
class GFG {
static int[] arr = new int[] { 4, 3, 7, 8, 6, 2, 1 };
// Method for zig-zag conversion of array
static void zigZag()
{
// Flag true indicates relation "<"
// is expected, else ">" is expected.
// The first expected relation
// is "<"
bool flag = true;
int temp = 0;
for (int i = 0; i <= arr.Length - 2; i++) {
// "<" relation expected
if (flag) {
// If we have a situation like A > B > C,
// we get A > C < B by swapping B and C
if (arr[i] > arr[i + 1]) {
// Swap
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
// ">" relation expected
else {
// If we have a situation like A < B < C,
// we get A < C > B by swapping B and C
if (arr[i] < arr[i + 1]) {
// Swap
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
// Flip flag
flag = !flag;
}
}
// Driver code
public static void Main(String[] args)
{
zigZag();
foreach(int i in arr) Console.Write(i + " ");
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// JavaScript program to sort an array
// in Zig-Zag form
// Program for zig-zag conversion of array
function zigZag(arr, n)
{
// Flag true indicates relation "<"
// is expected, else ">" is expected.
// The first expected relation is "<"
let flag = true;
for(let i = 0; i <= n - 2; i++)
{
// "<" relation expected
if (flag)
{
// If we have a situation like A > B > C,
// we get A > C < B by swapping B and C
if (arr[i] > arr[i + 1])
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
// ">" relation expected
else
{
// If we have a situation like A < B < C,
// we get A < C > B by swapping B and C
if (arr[i] < arr[i + 1])
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
// Flip flag
flag = !flag;
}
}
// Driver code
let arr = [ 4, 3, 7, 8, 6, 2, 1 ];
let n = arr.length;
zigZag(arr, n);
for(let i = 0; i < n; i++)
document.write(arr[i] + " ");
// This code is contributed by Surbhi Tyagi.
</script>
Output
3 7 4 8 2 6 1
Time complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
