Daily Python: Python Pool: Bitonic sort: Algorithm and Implementation in Python

Hello coders!! In this article, we will be learning about the python bitonic sort algorithm and its implementation in Python. Sorting is the way of arranging the elements in a specific order, i.e., either in ascending or descending order. There are various sorting algorithms available, all having their own pros and cons. The bitonic sort is a parallel sorting algorithm that sorts the elements through comparisons.

What is the Bitonic sort?

It is a sorting algorithm that runs parallel. In this algorithm, there are O(n2 log n) comparisons. Although the number of comparisons is more, it’s more suitable for parallel implementation because the elements are compared in a predefined sequence (the bitonic sequence) that doesn’t depend on data. Therefore it is optimal for implementation in hardware and parallel processor array.

What is the Bitonic sequence?

In this sequence, after some particular index, the elements start decreasing whereas before that index the elements come in increasing order.

x0 <= x1 …..<= xi  and  xi >= xi+1….. >= xn-1

A sequence in increasing order is said to be Bitonic with the decreasing part as empty. Similarly, the decreasing sequence is said to be Bitonic, with the increasing part as empty.
A Bitonic Sequence, when rotated, is also bitonic.

How to convert Random sequence to Bitonic sequence?

Let us first consider the following elements of an array

Random Sequence Elements

First, we will make pairs of elements. We will then create its bitonic sequence such that one is in ascending order and the other is in descending order and so on.

Taking pairs of two and sorting in first ascending then descending order

Now, we will make pairs of each pair such that every sequence has four elements.

Groups of four elements

Sorting first sequence in ascending order:

First compare the elements
Then compare the adjacent elements

Sorting the first half in ascending order

Similarly, we will sort the second sequence in descending order:

Sorting the second half in descending order

Now, we will merge these two to get our final bitonic sequence

Bitonic Sequence

Bitonic Sort Algorithm:

At first, we will create a bitonic sequence.
Next we need to compare and sort the corresponding elements of both the halves of the sequence
Now, we will compare and swap every second element of the sequence
At last, we will compare and swap adjacent elements of the sequence

Illustration of Bitonic Sort Algorithm:

Let us consider the above created bitonic sequence.

At first we will compare and sort the corresponding elements of both the halves of the sequence

Now compare and swap every second element of the sequence

We will now do the same for the adjacent elements

Source Code in Python:

def compare_swap(a, i, j, d):
    if (d == 1 and a[i] > a[j]) or (d == 0 and a[i] < a[j]):
        a[i], a[j] = a[j], a[i]
 

def merge(a, l, cnt, d):
    if cnt > 1:
        k = int(cnt / 2)
        for i in range(l, l + k):
            compare_swap(a, i, i + k, d)
        merge(a, l, k, d)
        merge(a, l + k, k, d)

def bitonic_sort(a, l, cnt, d):
    if cnt > 1:
        k = int(cnt / 2)
        bitonic_sort(a, l, k, 1)
        bitonic_sort(a, l + k, k, 0)
        merge(a, l, cnt, d)
 

def sort(a, N, u):
    bitonic_sort(a, 0, N, u)
 
a = [3, 4, 1, 9, 2, 7, 5, 6]
n=len(a)
   
u = 1
 
sort(a, n, u)
print("\nSorted array is")
for i in range(n):
    print("%d" % a[i])

Output:

Complexity Analysis:

Time complexity: O(log ² n)
Space complexity: O(n log ² n)

Advantages:

Memory is well handled by the process
Best suited for parallel processor array

Bitonic Sort vs Merge Sort:

Bitonic Sort	Merge Sort
Comparison based parallel algorithm	Divide and conquer algorithm
O(n Log ²n) comparisons are done	O(nLogn) comparisons are done
smaller numbers of each pair are moved to the left and larger numbers to right.	input array is divided into two halves and then the function calls itself for the two halves, and ultimately the sorted halves are merged
Time complexity: O(log ² n)	Time complexity: O(nLogn)

Must Read

Conclusion:

All sorting algorithms have their own pros and cons. Even though the number of comparisons in bitonic sort python is more, it is best suited for parallel arrays.

However, if you have any doubts or questions, do let me know in the comment section below. I will try to help you as soon as possible.

Happy Pythoning!

The post Bitonic sort: Algorithm and Implementation in Python appeared first on Python Pool.

from Planet Python
via read more

Daily Python

Sunday, January 3, 2021

Python Pool: Bitonic sort: Algorithm and Implementation in Python