[edu] Zigzag

A zigzag sorted sequence of integers a0,a1,a2,a3,a4,…$a_0,a_1,a_2,a_3,a_4,\dots$ is a sequence where

a0≥a1≤a2≥a3≤a4≥…$$a_0\ge a_1\le a_2\ge a_3\le a_4\ge \dots$$

In other words, the sequence alternates between larger and smaller integers: the first is larger than or equal to the second, the second is smaller than or equal to the third, the third is larger than or equal to the fourth, and so on. Here's an example of such a zigzag sorted sequence:

Given an unsorted sequence of integers, a simple way to rearrange the integers into a zigzag sorted sequence is to use sorting. First sort the integers in the sequence in increasing order, then swap each non-overlapping pair of adjacent integers. For example, let the original sequence be [10, 90, 49, 2, 1, 5, 23]. After sorting, we get [1, 2, 5, 10, 23, 49, 90]. After swapping adjacent elements, we get [2, 1, 10, 5, 49, 23, 90].

However, there's a faster way to zigzag sort a given sequence of integers that only requires a single traversal over the elements of the sequence. The idea is based on the fact that if we make sure that all even-positioned elements (at indices 0, 2, 4, …) are greater than or equal to their adjacent odd-positioned elements, we do no longer need to worry about the odd-positioned elements. All it requires is to traverse the even positions from left to right, and on each position execute the following two steps one after the other:

1. if the current element at the even position is less than the element on the previous odd position (if that position exists), swap both elements

2. if the current element at the even position is less than the element on the next odd position (if that position exists), swap both elements

If we apply this method to the above example, we get

Assignment

• Write a function isZigzag that takes a list or a tuple of integers. The function must return a Boolean value that indicates whether or not the given list or tuple of integers is zigzag sorted.

• Write a function zigzagSlow that takes a list of integers. The function must zigzag sort the given list of integers using the slow method described above. The function should not return a value, but must modify the given list in place.

• Write a function zigzagFast that takes a list of integers. The function must zigzag sort the given list of integers using the fast method described above. The function should not return a value, but must modify the given list in place.

Example

>>> isZigzag([10, 5, 6, 3, 2, 20, 100, 80])
False
>>> isZigzag((10, 5, 6, 2, 20, 3, 100, 80))
True
>>> isZigzag([20, 5, 10, 2, 80, 6, 100, 3])
True

>>> seq = [10, 90, 49, 2, 1, 5, 23]
>>> zigzagSlow(seq)
>>> seq
[2, 1, 10, 5, 49, 23, 90]

>>> seq = [10, 90, 49, 2, 1, 5, 23]
>>> zigzagFast(seq)
>>> seq
[90, 10, 49, 1, 5, 2, 23]

def isZigzag(nums):
    for i, num in enumerate(nums):
        if i % 2 == 0:
            idx_prev = i - 1
            idx_next = i + 1
            is_prev = idx_prev >= 0
            is_next = idx_next < len(nums)
            if is_prev and num < nums[idx_prev]:
                return False
            if is_next and num < nums[idx_next]:
                return False
    return True


def zigzagSlow(nums):
    nums.sort()
    for i, num in enumerate(nums):
        if i % 2 == 0:
            idx_next = i + 1
            is_next = idx_next < len(nums)
            if is_next and num < nums[idx_next]:
                nums[i], nums[idx_next] = nums[idx_next], nums[i]


def zigzagFast(nums):
    SIZE = len(nums)
    for _ in range(SIZE - 1):
        for i in range(SIZE):
            if i % 2 == 0:
                idx_prev = i - 1
                idx_next = i + 1
                is_prev = idx_prev >= 0
                is_next = idx_next < SIZE
                if is_prev and nums[i] < nums[idx_prev]:
                    nums[i], nums[idx_prev] = nums[idx_prev], nums[i]
                if is_next and nums[i] < nums[idx_next]:
                    nums[i], nums[idx_next] = nums[idx_next], nums[i]


seq = [10, 90, 49, 2, 1, 5, 23]
zigzagFast(seq)
print(seq)