1. Overview
In this article, We'll learn about how to implement Bitonic sort in java.
Bitonic Sort is a classic parallel sorting algorithm. This is called as Bitonic Mergesort. It is also used as a construction method for building a sorting network.
Basically, it is a procedure of Biotonic sequence using bitonic splits.
In java many sorting techniques can be implemented. But we have to choose the better one. This is very rarely used in real applications.
The bitonic sequence is said that when there is an index i exists such that either monotonically increasing and monotonically decreasing from index i and vice versa.
Eg. 7, 4, 2, 1, 9, 8, 7, 6, 5
In this example where values from index 0 to 3 values are in incremental order and from index 4 to 8 are in decreasing order. This is called monotonically decreasing or increasing. This is the type of sequence is said to be Biotonic Sequence Network.
Bitonic Splits is a procedure of splitting a bitonic sequence into a bitonic sequence of half length.
let us see the procedure to sort the given integer array using the Bitonic Sort technique.
This does take input an unsorted array and converts into a Biotonic Sequence. This conversion takes k(k-1)/2 steps.
2. Converting a random input into a Biotonic Sequence
We start by forming 4-element bitonic sequences from the consecutive 2-element sequence. Consider 4-element in sequence x0, x1, x2, x3. We sort x0 and x1 in ascending order and x2 and x3 in descending order. We then concatenate the two pairs to form a 4 element bitonic sequence.
Next, we take two 4 element bitonic sequences, sorting one in ascending order, the other in descending order (using the Bitonic Sort which we will discuss below), and so on, until we obtain the bitonic sequence.
3. Bitonic Sort Java Program
The following is the implementation of Bitonic Sort in java programming language.package com.java.w3schools.blog.sorting;
/* Java program for Bitonic Sort. Note that this program
works only when size of input is a power of 2. */
public class BitonicSort {
/*
* 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.
*/
void compAndSwap(int a[], int i, int j, int dir) {
if ((a[i] > a[j] && dir == 1) || (a[i] < a[j] && dir == 0)) {
// Swapping elements
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
/*
* 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.
*/
void bitonicMerge(int a[], int low, int cnt, int dir) {
if (cnt > 1) {
int k = cnt / 2;
for (int i = low; i < low + k; i++)
compAndSwap(a, i, i + k, dir);
bitonicMerge(a, low, k, dir);
bitonicMerge(a, low + k, k, dir);
}
}
/*
* 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
*/
void bitonicSort(int a[], int low, int cnt, int dir) {
if (cnt > 1) {
int k = cnt / 2;
// sort in ascending order since dir here is 1
bitonicSort(a, low, k, 1);
// sort in descending order since dir here is 0
bitonicSort(a, low + k, k, 0);
// Will merge wole sequence in ascending order
// since dir=1.
bitonicMerge(a, low, cnt, dir);
}
}
/*
* Caller of bitonicSort for sorting the entire array of length N in ASCENDING
* order
*/
void sort(int a[], int N, int up) {
bitonicSort(a, 0, N, up);
}
/* A utility function to print array of size n */
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver method
public static void main(String args[]) {
int a[] = { 3, 7, 4, 8, 6, 2, 1, 5 };
int up = 1;
BitonicSort ob = new BitonicSort();
ob.sort(a, a.length, up);
System.out.println("\nSorted array");
printArray(a);
}
}
Output:
Sorted array:
1 2 3 4 5 6 7 8
4. Conclusion
In this article, We've seen how to implement the Bitonic Sorting technique in Java language.
For this, we must know what is Biotonic Sequence. We have discussed how to convert a random array into a Bitonic sequence.
Finally seen how to implement a java program with output.
As usual, the code shown here is over GitHub.
Reference
0 Comments