$show=/label

Java Program to Bitonic Sort

SHARE:

A quick practical working java program for Bitonic sort. Explained how Bitonic Sequence works with examples.

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.


Java Program to Bitonic Sort



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

COMMENTS

BLOGGER

About Us

Author: Venkatesh - I love to learn and share the technical stuff.
Name

accumulo,1,ActiveMQ,2,Adsense,1,API,37,ArrayList,16,Arrays,7,Bean Creation,3,Bean Scopes,1,BiConsumer,1,Blogger Tips,1,Books,1,C Programming,1,Collection,5,Collections,22,Collector,1,Command Line,1,Compile Errors,1,Configurations,7,Constants,1,Control Statements,8,Conversions,6,Core Java,81,Corona India,1,Create,2,CSS,1,Date,3,Date Time API,4,Dictionary,1,Difference,1,Download,1,Eclipse,2,Efficiently,1,Error,1,Errors,1,Exception,1,Exceptions,3,Fast,1,Files,9,Float,1,Font,1,Form,1,Freshers,1,Function,3,Functional Interface,2,Garbage Collector,1,Generics,4,Git,4,Grant,1,Grep,1,HashMap,1,HomeBrew,2,HTML,2,HttpClient,2,Immutable,1,Installation,1,Interview Questions,5,Iterate,2,Jackson API,3,Java,29,Java 10,1,Java 11,5,Java 12,5,Java 13,2,Java 14,2,Java 8,66,Java 8 Difference,2,Java 8 Stream Conversions,2,java 8 Stream Examples,3,Java 9,1,Java Conversions,11,Java Design Patterns,1,Java Files,1,Java Program,2,Java Programs,65,java.lang,5,java.util. function,1,jQuery,1,Kotlin,10,Kotlin Conversions,3,Kotlin Programs,6,Lambda,1,lang,29,Leap Year,1,live updates,1,Logging,1,Mac OS,2,Math,1,Maven,1,Method References,1,Mockito,1,MongoDB,3,New Features,1,Operations,1,Optional,6,Oracle,5,Oracle 18C,1,Partition,1,Patterns,1,Programs,1,Property,1,Python,2,Quarkus,1,Read,1,Real Time,1,Recursion,2,Remove,2,Rest API,1,Schedules,1,Serialization,1,Servlet,1,Sort,1,Sorting Techniques,8,Spring,2,Spring Boot,23,Spring Email,1,Spring MVC,1,Streams,21,String,58,String Programs,9,String Revese,1,Swing,1,System,1,Tags,1,Threads,10,Tomcat,1,Tomcat 8,1,Troubleshoot,16,Unix,2,Updates,3,util,5,While Loop,1,
ltr
item
JavaProgramTo.com: Java Program to Bitonic Sort
Java Program to Bitonic Sort
A quick practical working java program for Bitonic sort. Explained how Bitonic Sequence works with examples.
https://1.bp.blogspot.com/-IMwGpXVu8mw/XS31DWo9ZYI/AAAAAAAABuk/xKGzCO8DKqgDNmS3fzRx-5XkMQdXWkd5QCLcBGAs/s320/Java%2BProgram%2Bto%2BBitonic%2BSort.png
https://1.bp.blogspot.com/-IMwGpXVu8mw/XS31DWo9ZYI/AAAAAAAABuk/xKGzCO8DKqgDNmS3fzRx-5XkMQdXWkd5QCLcBGAs/s72-c/Java%2BProgram%2Bto%2BBitonic%2BSort.png
JavaProgramTo.com
https://www.javaprogramto.com/2019/07/java-bitonic-sort.html
https://www.javaprogramto.com/
https://www.javaprogramto.com/
https://www.javaprogramto.com/2019/07/java-bitonic-sort.html
true
3124782013468838591
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS PREMIUM CONTENT IS LOCKED STEP 1: Share to a social network STEP 2: Click the link on your social network Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy Table of Content