Open In App

Python Program for Bitonic Sort

Last Updated : 03 Aug, 2022
Improve
Improve
Like Article
Like
Save
Share
Report

Bitonic Sequence: A sequence is called Bitonic if it is first increasing, then decreasing. In other words, an array arr[0..n-i] is Bitonic if there exists an index i where 0<=i<=n-1 such that 

x0 <= x1 …..<= xi  and  xi >= xi+1….. >= xn-1
  1. A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty. Similarly, decreasing order sequence is considered Bitonic with the increasing part as empty.
  2. A rotation of the Bitonic Sequence is also bitonic.

Bitonic Sorting: It mainly involves two steps.  

  1. Forming a bitonic sequence (discussed above in detail). After this step we reach the fourth stage in below diagram, i.e., the array becomes {3, 4, 7, 8, 6, 5, 2, 1}
  2. Creating one sorted sequence from the bitonic sequence: After the first step, the first half is sorted in increasing order and the second half in decreasing order. 
    We compare the first element of the first half with the first element of the second half, then the second element of the first half with the second element of second and so on. We exchange elements if an element of the first half is smaller. 
    After the above compare and exchange steps, we get two bitonic sequences in the array. See the fifth stage below the diagram. In the fifth stage, we have {3, 4, 2, 1, 6, 5, 7, 8}. If we take a closer look at the elements, we can notice that there are two bitonic sequences of length n/2 such that all elements in the first bitonic sequence {3, 4, 2, 1} are smaller than all elements of the second bitonic sequence {6, 5, 7, 8}. 
    We repeat the same process within two bitonic sequences and we get four bitonic sequences of length n/4 such that all elements of the leftmost bitonic sequence are smaller and all elements of the rightmost. See sixth stage in below diagram, arrays is {2, 1, 3, 4, 6, 5, 7, 8}. 
    If we repeat this process one more time we get 8 bitonic sequences of size n/8 which is 1. Since all these bitonic sequences are sorted and every bitonic sequence has one element, we get the sorted array.

Example

Python3




# Python program for Bitonic Sort. Note that this program
# works only when size of input is a power of 2.
 
# The parameter dir indicates the sorting direction, ASCENDING
# or DESCENDING; if (a[i] > a[j]) agrees with the direction,
# then a[i] and a[j] are interchanged.*/
 
 
def compAndSwap(a, i, j, dire):
    if (dire == 1 and a[i] > a[j]) or (dire == 0 and a[i] > a[j]):
        a[i], a[j] = a[j], a[i]
 
# It recursively sorts a bitonic sequence in ascending order,
# if dir = 1, and in descending order otherwise (means dir=0).
# The sequence to be sorted starts at index position low,
# the parameter cnt is the number of elements to be sorted.
 
 
def bitonicMerge(a, low, cnt, dire):
    if cnt > 1:
        k = cnt//2
        for i in range(low, low+k):
            compAndSwap(a, i, i+k, dire)
        bitonicMerge(a, low, k, dire)
        bitonicMerge(a, low+k, k, dire)
 
# This function first produces a bitonic sequence by recursively
# sorting its two halves in opposite sorting orders, and then
# calls bitonicMerge to make them in the same order
 
 
def bitonicSort(a, low, cnt, dire):
    if cnt > 1:
        k = cnt//2
        bitonicSort(a, low, k, 1)
        bitonicSort(a, low+k, k, 0)
        bitonicMerge(a, low, cnt, dire)
 
# Caller of bitonicSort for sorting the entire array of length N
# in ASCENDING order
 
 
def sort(a, N, up):
    bitonicSort(a, 0, N, up)
 
 
# Driver code to test above
a = [3, 7, 4, 8, 6, 2, 1, 5]
n = len(a)
up = 1
 
sort(a, n, up)
print("\n\nSorted array is")
for i in range(n):
    print("%d" % a[i], end=" ")
 






                        










Output: 


Sorted array is
1 5 2 6 3 7 4 8




Time Complexity: O(n*log2(n))


Auxiliary Space: O(n*log2(n))




Please refer complete article on Bitonic Sort for more details!




                                    


                                                                        

                                        

                                            

                                                

                                                    

        https://media.geeksforgeeks.org/auth/avatar.png
       
                                                

                                                

                                                    
    

        

            GeeksforGeeks
        

    
                                                

                                            

                                                                                    

                                        

                                            
    

        
        
    
                                            

                                                
                                                
                                            

                                            

                                            Improve
                                                
                                            

                                        

                                    



                            

                                                            

                                    
                                        
                                        Previous Article
                                    
                                    
                                    

                                        Python Program for Cocktail Sort
                                    

                                

                                                            

                                    
                                        Next Article
                                        
                                    
                                    
                                    

                                        Python Program for Pigeonhole Sort
                                    

                                

                                                        

                            

            

                

                    

                    
                
 
                
    
                            

                                

                            


                            


            

        
  
                        

                                                

                        
                                                    

                                
Similar Reads

                                

                                    
        
            

                
Python Program to Find the Longest Bitonic Subsequence

                
Given an array arr[0 ... n-1] containing n positive integers, a subsequence of arr[] is called Bitonic if it is first increasing, then decreasing. Write a function that takes an array as argument and returns the length of the longest bitonic subsequence. A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty.

            

            
            

                
                3 min read
            

        
    
        
            

                
Python Program for Odd-Even Sort / Brick Sort

                
This is basically a variation of bubble-sort. This algorithm is divided into two phases- Odd and Even Phase. The algorithm runs until the array elements are sorted and in each iteration two phases occurs- Odd and Even Phases. In the odd phase, we perform a bubble sort on odd indexed elements and in the even phase, we perform a bubble sort on even i

            

            
            

                
                2 min read
            

        
    
        
            

                
Sort a Dictionary Without Using Sort Function in Python

                
As we all know Dictionaries in Python are unordered by default, which means they can’t be sorted directly. However, we can sort the keys or values of a dictionary and create a new sorted dictionary from the sorted keys or values. We can sort a list in a Dictionary using the inbuilt dictionary sort() function. But in this article, we will learn how

            

            
            

                
                3 min read
            

        
    
        
            

                
Python program to Sort a List of Tuples in Increasing Order by the Last Element in Each Tuple

                
The task is to write a Python Program to sort a list of tuples in increasing order by the last element in each tuple. Input: [(1, 3), (3, 2), (2, 1)] Output: [(2, 1), (3, 2), (1, 3)] Explanation: sort tuple based on the last digit of each tuple. Methods #1: Using sorted(). Sorted() method sorts a list and always returns a list with the elements in

            

            
            

                
                7 min read
            

        
    
        
            

                
Python Program for Selection Sort

                
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array. Python Program for Selection SortThe provided Python code demonstrates the Selection Sort algorithm. Selection Sort has a time

            

            
            

                
                2 min read
            

        
    
        
            

                
Python Program for Insertion Sort

                
Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands. Python Program for Insertion SortThe insertionSort function takes an array arr as input. It first calculates the length of the array (n). If the length is 0 or 1, the function returns immediately as an array with 0 or 1 element is considered already

            

            
            

                
                2 min read
            

        
    
        
            

                
Python Program for Counting Sort

                
Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then do some arithmetic to calculate the position of each object in the output sequence. Python Program for Counting SortThe provided Python code demonstrates Counting Sort, a non-comp

            

            
            

                
                4 min read
            

        
    
        
            

                
Python Program for Radix Sort

                
In this article we are going to see Radix Sort with Python Radix Sort Algorithm PythonThe provided Python code implements Radix Sort, a non-comparative sorting algorithm that works by distributing elements into buckets based on their individual digits. The code defines a countingSort function, which performs counting sort based on the digit represe

            

            
            

                
                3 min read
            

        
    
        
            

                
Python Program for Counting Sort

                
Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence. C/C++ Code # Python program for counting sort # The main function that sort the given string

            

            
            

                
                2 min read
            

        
    
        
            

                
Python Program for Binary Insertion Sort

                
We can use binary search to reduce the number of comparisons in normal insertion sort. Binary Insertion Sort find use binary search to find the proper location to insert the selected item at each iteration. In normal insertion, sort it takes O(i) (at ith iteration) in worst case. we can reduce it to O(logi) by using binary search. Python Program fo

            

            
            

                
                3 min read
            

        
                                    

                                                                    
                                                            

                        

                        

                                                            

                                    
Article Tags : 

                                    
                                                                    

                                                                                

                                                

                                

                                    
                                                                    

                            


                        

                            

                                                                                    

                              

                            

                                                        
                        

                    

                

            

        
        


        

                




	
	
	

	
	

	
	    

	
	

	
	



                
        

    

    

        

            

            

        

    















	

    
  

  
  








    
        We use cookies to ensure you have the best browsing experience on our website. By using our site, you
        acknowledge that you have read and understood our
        Cookie Policy &
        Privacy Policy
            
    







   Lightbox