Python Data Structures and Algorithms: Create a program for Bitonic Sort
Python Search and Sorting : Exercise-11 with Solution
Write a Python code to create a program for Bitonic Sort.
Bitonic Sort: According to rutgers.edu - Bitonic sort is a comparison-based sorting algorithm that can be run in parallel. It focuses on converting a random sequence of numbers into a bitonic sequence, one that monotonically increases, then decreases. Rotations of a bitonic sequence are also bitonic.
More specifically, bitonic sort can be modelled as a type of sorting network. The initial unsorted sequence enters through input pipes, where a series of comparators switch two entries to be in either increasing or decreasing order.
The algorithm, created by Ken Batcher in 1968, consists of two parts. First, the unsorted sequence is built into a bitonic sequence; then, the series is split multiple times into smaller sequences until the input is in sorted order.
License: https://bit.ly/2InTS3W # 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 = int(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 funcion 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 = int(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 =  print("How many numbers u want to enter?"); n = int(input()) print("Input the numbers:"); for i in range(n): a.append(int(input())) up = 1 sort(a, n, up) print("\n\nSorted array is:") for i in range(n): print("%d" % a[i])
How many numbers u want to enter? 5 Input the numbers: 25 13 76 59 37 Sorted array is: 13 25 59 76 37
Python Code Editor:
Contribute your code and comments through Disqus.
What is the difficulty level of this exercise?
- New Content published on w3resource :
- Python Numpy exercises
- Python GeoPy Package exercises
- Python Pandas exercises
- Python nltk exercises
- Python BeautifulSoup exercises
- Form Template
- Composer - PHP Package Manager
- PHPUnit - PHP Testing
- Laravel - PHP Framework