Printing an Array in Zigzag Fashion: A Comprehensive Guide

Printing an Array in Zigzag Fashion: A Comprehensive Guide

Sorting an array into a zigzag pattern is a common programming problem where the goal is to rearrange the elements such that the result alternates between less-than and greater-than relationships. Specifically, the output array should satisfy:e1<e2>e3<e4>e5…e_1 < e_2 > e_3 < e_4 > e_5 \dotsThis article will guide you through the problem, explain the algorithm, and provide a Python implementation.Printing an Array in Zigzag Fashion

Problem Statement

Given an array of integers, rearrange its elements into a zigzag pattern where:
  • The first element is less than the second.
  • The second element is greater than the third.
  • The third element is less than the fourth, and so on.

Example Test Cases

Test Case 1:

Input: 7,4,3,7,8,6,2,17, 4, 3, 7, 8, 6, 2, 1Output: 3,7,4,8,2,6,13, 7, 4, 8, 2, 6, 1

Test Case 2:

Input: 1,4,3,21, 4, 3, 2Output: 1,4,2,31, 4, 2, 3

Algorithm: Zigzag Sorting

Approach

  1. Iterate Through the Array: Traverse the array and compare adjacent elements.
  2. Alternate Comparisons:
    • If the current index is even, ensure the current element is less than the next.
    • If the current index is odd, ensure the current element is greater than the next.
  3. Swap When Necessary: If the condition is not satisfied, swap the two elements to restore the zigzag order.

Complexity

  • Time Complexity: O(n)O(n) — We only traverse the array once.
  • Space Complexity: O(1)O(1) — In-place modification of the array.

Python Implementation

python
def zigzag_array(arr): """ Rearrange the array in zigzag fashion: e1 < e2 > e3 < e4 > ... Args: arr (list): List of integers. Returns: list: Zigzag patterned array. """ n = len(arr)# Iterate through the array for i in range(n - 1): # For even index, check if arr[i] < arr[i+1] if i % 2 == 0: if arr[i] > arr[i + 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] # For odd index, check if arr[i] > arr[i+1] else: if arr[i] < arr[i + 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i]return arr# Example Test Cases print(zigzag_array([4, 3, 7, 8, 6, 2, 1])) # Output: [3, 7, 4, 8, 2, 6, 1] print(zigzag_array([1, 4, 3, 2])) # Output: [1, 4, 2, 3]

Explanation of Test Cases

Input: 4,3,7,8,6,2,14, 3, 7, 8, 6, 2, 1

  1. At index 0 (even), check 4<34 < 3. Condition fails, swap: [3,4,7,8,6,2,1][3, 4, 7, 8, 6, 2, 1].
  2. At index 1 (odd), check 4>74 > 7. Condition fails, swap: [3,7,4,8,6,2,1][3, 7, 4, 8, 6, 2, 1].
  3. At index 2 (even), check 4<84 < 8. Condition holds, no change.
  4. At index 3 (odd), check 8>68 > 6. Condition holds, no change.
  5. At index 4 (even), check 6<26 < 2. Condition fails, swap: [3,7,4,8,2,6,1][3, 7, 4, 8, 2, 6, 1].
  6. At index 5 (odd), check 6>16 > 1. Condition holds, no change.
Output: [3,7,4,8,2,6,1][3, 7, 4, 8, 2, 6, 1]Click here to know more our program! 
c