Print an Array in Zigzag Order | Step-by-Step Guide

Print an Array in Zigzag Order | Step-by-Step Guide

Print an Array in Zigzag Order | Step-by-Step 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 \dots

This article will guide you through the problem, explain the algorithm, and provide a Python implementation.

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, 1

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

Test Case 2:

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

Output:
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]