sorts.bitonic_sort¶
Python program for Bitonic Sort.
Note that this program works only when size of input is a power of 2.
Attributes¶
Functions¶
|
It recursively sorts a bitonic sequence in ascending order, if direction = 1, and in |
|
This function first produces a bitonic sequence by recursively sorting its two |
|
Compare the value at given index1 and index2 of the array and swap them as per |
Module Contents¶
- sorts.bitonic_sort.bitonic_merge(array: list[int], 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(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]
- sorts.bitonic_sort.comp_and_swap(array: list[int], 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¶