Python:實現bitonic sort雙調排序算法(附完整源碼)

Python:實現bitonic sort雙調排序算法

from __future__ import annotations
def comp_and_swap(array: list[int], index1: int, index2: int, direction: int) -> None:
if (direction == 1 and array[index1] > array[index2]) or (
direction == 0 and array[index1] < array[index2]
):
array[index1], array[index2] = array[index2], array[index1]
def bitonic_merge(array: list[int], low: int, length: int, direction: int) -> None:
if length > 1:
middle = int(length / 2)
for i in range(low, low + middle):
comp_and_swap(array, i, i + middle, direction)
bitonic_merge(array, low, middle, direction)
bitonic_merge(array, low + middle, middle, direction)
def bitonic_sort(array: list[int], low: int, length: int, direction: int) -> None:
""" This function first produces a bitonic sequence by recursively sorting its two halves in opposite sorting orders, and then calls bitonic_merge to make them in the same order. >>> arr = [12, 34, 92, -23, 0, -121, -167, 145] >>> bitonic_sort(arr, 0, 8, 1) >>> arr [-167, -121, -23, 0, 12, 34, 92, 145] >>> bitonic_sort(arr, 0, 8, 0) >>> arr [145, 92, 34, 12, 0, -23, -121, -167] """
if length > 1:
middle = int(length / 2)
bitonic_sort(array, low, middle, 1)
bitonic_sort(array, low + middle, middle, 0)
bitonic_merge(array, low, length, direction)
if __name__ == "__main__":
user_input = input("Enter numbers separated by a comma:\n").strip()
unsorted = [int(item.strip()) for item in user_input.split(",")]
bitonic_sort(unsorted, 0, len(unsorted), 1)
print("\nSorted array in ascending order is: ", end="")
print(*unsorted, sep=", ")
bitonic_merge(unsorted, 0, len(unsorted), 0)
print("Sorted array in descending order is: ", end="")
print(*unsorted, sep=", ")