TheAlgorithms-Python

1
"""
2
Python program for Bitonic Sort.
3

4
Note that this program works only when size of input is a power of 2.
5
"""
6

7
from __future__ import annotations
8

9

10
def comp_and_swap(array: list[int], index1: int, index2: int, direction: int) -> None:
11
    """Compare the value at given index1 and index2 of the array and swap them as per
12
    the given direction.
13

14
    The parameter direction indicates the sorting direction, ASCENDING(1) or
15
    DESCENDING(0); if (a[i] > a[j]) agrees with the direction, then a[i] and a[j] are
16
    interchanged.
17

18
    >>> arr = [12, 42, -21, 1]
19
    >>> comp_and_swap(arr, 1, 2, 1)
20
    >>> arr
21
    [12, -21, 42, 1]
22

23
    >>> comp_and_swap(arr, 1, 2, 0)
24
    >>> arr
25
    [12, 42, -21, 1]
26

27
    >>> comp_and_swap(arr, 0, 3, 1)
28
    >>> arr
29
    [1, 42, -21, 12]
30

31
    >>> comp_and_swap(arr, 0, 3, 0)
32
    >>> arr
33
    [12, 42, -21, 1]
34
    """
35
    if (direction == 1 and array[index1] > array[index2]) or (
36
        direction == 0 and array[index1] < array[index2]
37
    ):
38
        array[index1], array[index2] = array[index2], array[index1]
39

40

41
def bitonic_merge(array: list[int], low: int, length: int, direction: int) -> None:
42
    """
43
    It recursively sorts a bitonic sequence in ascending order, if direction = 1, and in
44
    descending if direction = 0.
45
    The sequence to be sorted starts at index position low, the parameter length is the
46
    number of elements to be sorted.
47

48
    >>> arr = [12, 42, -21, 1]
49
    >>> bitonic_merge(arr, 0, 4, 1)
50
    >>> arr
51
    [-21, 1, 12, 42]
52

53
    >>> bitonic_merge(arr, 0, 4, 0)
54
    >>> arr
55
    [42, 12, 1, -21]
56
    """
57
    if length > 1:
58
        middle = int(length / 2)
59
        for i in range(low, low + middle):
60
            comp_and_swap(array, i, i + middle, direction)
61
        bitonic_merge(array, low, middle, direction)
62
        bitonic_merge(array, low + middle, middle, direction)
63

64

65
def bitonic_sort(array: list[int], low: int, length: int, direction: int) -> None:
66
    """
67
    This function first produces a bitonic sequence by recursively sorting its two
68
    halves in opposite sorting orders, and then calls bitonic_merge to make them in the
69
    same order.
70

71
    >>> arr = [12, 34, 92, -23, 0, -121, -167, 145]
72
    >>> bitonic_sort(arr, 0, 8, 1)
73
    >>> arr
74
    [-167, -121, -23, 0, 12, 34, 92, 145]
75

76
    >>> bitonic_sort(arr, 0, 8, 0)
77
    >>> arr
78
    [145, 92, 34, 12, 0, -23, -121, -167]
79
    """
80
    if length > 1:
81
        middle = int(length / 2)
82
        bitonic_sort(array, low, middle, 1)
83
        bitonic_sort(array, low + middle, middle, 0)
84
        bitonic_merge(array, low, length, direction)
85

86

87
if __name__ == "__main__":
88
    user_input = input("Enter numbers separated by a comma:\n").strip()
89
    unsorted = [int(item.strip()) for item in user_input.split(",")]
90

91
    bitonic_sort(unsorted, 0, len(unsorted), 1)
92
    print("\nSorted array in ascending order is: ", end="")
93
    print(*unsorted, sep=", ")
94

95
    bitonic_merge(unsorted, 0, len(unsorted), 0)
96
    print("Sorted array in descending order is: ", end="")
97
    print(*unsorted, sep=", ")
98