Python Program for Bitonic Sort

The bitonic sort is a parallel sorting algorithm that uses comparisons to order the items. In this tutorial, we will sort an array with help of a bitonic sort algorithm.

Bitonic Sort - Basic Introduction

It's a parallel-processing sorting algorithm. There are O(n2 log n) comparisons in this algorithm. Despite the higher number of comparisons, it is more suited to parallel implementation since the components are compared in a preset sequence (the bitonic sequence) that is independent of data. As a result, it's best for hardware and parallel processor array implementation.

• Bitonic sort may be modeled as a form of sorting network in more detail. The unsorted sequence is sent into input pipes, where a series of comparators switch two entries into increasing or decreasing order.
• Bitonic Sequence: "x0 <= x1 …..<= xi and xi >= xi+1….. >= xn-1", A Bitonic sequence is one in which the lowering section is empty and the growing part is in ascending order. The diminishing sequence is also known as Bitonic, with the growing section being empty.

Let us now have a look at the working of Bitonic Sort:

1. Create a bitonic sequence
2. Compare and sort the corresponding element of both half of the sequence
3. Compare and swap every second element of the sequence
4. Compare and swap the adjacent elements of the sequence
5. The resultant list is sort one

See the figure below for the reference of working of Bitonic Sort:

Algorithm

As of now, we have a rough understanding of how bitonic sort is performed. For better understanding let's dive deep into the algorithm followed by the code:

1. Define a function c_swap() and pass 4 parameters
2. Create a sequence
3. The sequence is to be sorted at the index position
4. Define a function Merge() and pass 4 parameters
5. The merge function will recursively produce a bitonic function
6. Sort its two halves in opposite sorting order
7. Call Merge() function
8. Create a function bitonic_sort() and pass 4 parameters
9. Create a sort() function to sort the array in ascending order
10. The resulting array will be sorted
11. Print the array

Program for Bitonic Sort

As discussed above in the algorithm, let us now dive into the programming part of the Bitonic Sort operation influenced by the algorithm.

def c_swap(a, b, c, d):
    if (d == 1 and a[b] > a[c]) or (d == 0 and a[b] < a[c]):
        a[b], a[c] = a[c], a[b]

def merge(a, b, cnt, d):
    if cnt > 1:
        k = int(cnt / 2)
        for i in range(b, b + k):
            c_swap(a, i, i + k, d)
        merge(a, b, k, d)
        merge(a, b + k, k, d)
 
def bitonic_sort(a, b, cnt, d):
    if cnt > 1:
        k = int(cnt / 2)
        bitonic_sort(a, b, k, 1)
        bitonic_sort(a, b + k, k, 0)
        merge(a, b, cnt, d)
  
def sort(a, B, u):
    bitonic_sort(a, 0, B, u)

# driver code   
a = [2, 10, 20, 5, 3, 4]
n=len(a)
print("The original array is:", a)    
u = 1
  
sort(a, n, u)
print("Sorted array is", a)

The original array is: [2, 10, 20, 30, 5, 5, 4, 3]
Sorted array is [2, 3, 4, 5, 5, 10, 20, 30]

Conclusion

In this tutorial, we have performed a bitonic sort operation in python to sort an array. The memory is best handled by this algorithm. The time complexity of bitonic sort is O(log ² n) and the space complexity is O(n log ² n).