sorts.bitonic_sort

Python program for Bitonic Sort.

Note that this program works only when size of input is a power of 2.

Attributes

user_input

Classes

Comparable

Base class for protocol classes.

Functions

bitonic_merge(→ None)	It recursively sorts a bitonic sequence in ascending order, if direction = 1, and in
bitonic_sort(→ None)	This function first produces a bitonic sequence by recursively sorting its two
comp_and_swap(→ None)	Compare the value at given index1 and index2 of the array and swap them as per

Module Contents

class sorts.bitonic_sort.Comparable

Bases: Protocol

Base class for protocol classes.

Protocol classes are defined as:

class Proto(Protocol):
    def meth(self) -> int:
        ...

Such classes are primarily used with static type checkers that recognize structural subtyping (static duck-typing).

For example:

class C:
    def meth(self) -> int:
        return 0

def func(x: Proto) -> int:
    return x.meth()

func(C())  # Passes static type check

See PEP 544 for details. Protocol classes decorated with @typing.runtime_checkable act as simple-minded runtime protocols that check only the presence of given attributes, ignoring their type signatures. Protocol classes can be generic, they are defined as:

class GenProto[T](Protocol):
    def meth(self) -> T:
        ...

__lt__(other: object, /) → bool

sorts.bitonic_sort.bitonic_merge[T: Comparable](array: list[T], low: int, length: int, direction: int) → None

It recursively sorts a bitonic sequence in ascending order, if direction = 1, and in descending if direction = 0. The sequence to be sorted starts at index position low, the parameter length is the number of elements to be sorted.

>>> arr = [12, 42, -21, 1]
>>> bitonic_merge(arr, 0, 4, 1)
>>> arr
[-21, 1, 12, 42]

>>> bitonic_merge(arr, 0, 4, 0)
>>> arr
[42, 12, 1, -21]

sorts.bitonic_sort.bitonic_sort[T: Comparable](array: list[T], 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]

>>> arr = ["banana", "apple", "cherry", "date"]
>>> bitonic_sort(arr, 0, 4, 1)
>>> arr
['apple', 'banana', 'cherry', 'date']

>>> arr = [3, 1.5, 2, 4.5]
>>> bitonic_sort(arr, 0, 4, 1)
>>> arr
[1.5, 2, 3, 4.5]

>>> arr = [1, "two", 3, "four"]
>>> bitonic_sort(arr, 0, 4, 1)
Traceback (most recent call last):
...
TypeError: '<' not supported between instances of 'str' and 'int'

sorts.bitonic_sort.comp_and_swap[T: Comparable](array: list[T], index1: int, index2: int, direction: int) → None

Compare the value at given index1 and index2 of the array and swap them as per the given direction.

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

>>> arr = [12, 42, -21, 1]
>>> comp_and_swap(arr, 1, 2, 1)
>>> arr
[12, -21, 42, 1]

>>> comp_and_swap(arr, 1, 2, 0)
>>> arr
[12, 42, -21, 1]

>>> comp_and_swap(arr, 0, 3, 1)
>>> arr
[1, 42, -21, 12]

>>> comp_and_swap(arr, 0, 3, 0)
>>> arr
[12, 42, -21, 1]

sorts.bitonic_sort.user_input