mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 13:33:11 +08:00
Ewan John Dennisandpre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
b0e607a1b2
* Fix negative indexing bug and improve readability in wiggle_sort Issue: - The previous implementation used `enumerate(nums)`, starting the loop at `i = 0`. This caused `nums[i - 1]` to evaluate to `nums[-1]`, accidentally comparing (and potentially swapping) the first element with the last element of the array on the first iteration. - The conditional logic `(i % 2 == 1) == (nums[i - 1] > nums[i])` was convoluted, hard to read, and triggered unnecessary swaps when adjacent numbers were equal. Fix: - Changed the loop to use `range(1, len(nums))` to ensure the index safely starts at 1, eliminating the negative indexing bug. - Replaced the confusing equality check with explicit `if/elif` statements that clearly define the peak (odd indices) and valley (even indices) requirements of a Wiggle Sort. - Preserved all original docstrings and the __main__ block as-is. * [pre-commit.ci] auto fixes from pre-commit.com hooks for more information, see https://pre-commit.ci * Combine conditional branches to satisfy ruff linting - Updated `wiggle_sort` logic to merge the odd and even swap conditions using a single `or` expression. - Fixes SIM114 ruff linter check failure (`Combine if branches using logical or operator`). * [pre-commit.ci] auto fixes from pre-commit.com hooks for more information, see https://pre-commit.ci * Update doctests in wiggle_sort to match fixed implementation output - Updated expected outputs for negative array doctests in `sorts/wiggle_sort.py`. - The previous doctest expectations relied on the incorrect behavior caused by the index-0 negative lookup bug. - Fixes pytest doctest mismatch failure in CI build job. --------- Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
43 lines
1.0 KiB
Python
43 lines
1.0 KiB
Python
"""
|
|
Wiggle Sort.
|
|
|
|
Given an unsorted array nums, reorder it such
|
|
that nums[0] < nums[1] > nums[2] < nums[3]....
|
|
For example:
|
|
if input numbers = [3, 5, 2, 1, 6, 4]
|
|
one possible Wiggle Sorted answer is [3, 5, 1, 6, 2, 4].
|
|
"""
|
|
|
|
|
|
def wiggle_sort(nums: list) -> list:
|
|
"""
|
|
Python implementation of wiggle sort.
|
|
Reorders an array such that nums[0] <= nums[1] >= nums[2] <= nums[3]...
|
|
|
|
Example:
|
|
>>> wiggle_sort([0, 5, 3, 2, 2])
|
|
[0, 5, 2, 3, 2]
|
|
>>> wiggle_sort([])
|
|
[]
|
|
>>> wiggle_sort([-2, -5, -45])
|
|
[-5, -2, -45]
|
|
>>> wiggle_sort([-2.1, -5.68, -45.11])
|
|
[-5.68, -2.1, -45.11]
|
|
"""
|
|
for i in range(1, len(nums)):
|
|
if (i % 2 == 1 and nums[i - 1] > nums[i]) or (
|
|
i % 2 == 0 and nums[i - 1] < nums[i]
|
|
):
|
|
nums[i - 1], nums[i] = nums[i], nums[i - 1]
|
|
|
|
return nums
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print("Enter the array elements:")
|
|
array = list(map(int, input().split()))
|
|
print("The unsorted array is:")
|
|
print(array)
|
|
print("Array after Wiggle sort:")
|
|
print(wiggle_sort(array))
|