Implementation of Bitonic Sort in C++

Hello, Learners today we will learn Bitonic Sort and implement it in C++ programming. The Bitonic sort is a sorting algorithm whose time complexity is O(n log2n).

Unlike Merge sort and Insertion sort, the Bitonic sort Algorithm has much more total number of comparisons. Despite large time complexity Bitonic Sort is used because for parallel implementation this is better than other algorithms, The reason is sorting in this algorithm is done on the predefined sequence (here Bitonic sequence), and the sequence of comparison of any algorithm does not depend on data.

Before going into detail of Bitonic Sort first, let us see what is Bitonic sequence and how it is obtained from the original data sequence.

Bitonic Sequence

If elements of a sequence are first in increasing order and then in decreasing order then that sequence of data is called a Bitonic Sequence. Suppose there is an array of n+1 elements say arr[0, n]. Then there is an index value ‘i’ such that

arr[0] <= arr[1] <= … <= arr[i] >= arr[i+1] >= arr[i+2] >= … >= arr[i+2]

For example, array  = {1, 4, 6, 5} is a Bitonic sequence because the first half is in increasing order and second half in decreasing order.

Let us see how to convert a data sequence in the Bitonic sequence

The Smallest Bitonic sequence we can form is of 4-elements in which the first two elements are in increasing order and the last two elements are in decreasing order and together they form a Bitonic sequence. Here we start by forming the 4-element bitonic sequence and then we take two 4-elements bitonic sequences one sorting in increasing and other in decreasing order (using Bitonic Sort) and hence we obtain 8-element Bitonic sequence. We repeat this until we obtain a single Bitonic sequence of all data elements.

Example

Convert the sequence {8, 3, 5, 1, 7, 9, 2, 4} to Bitonic sequence.

Bitonic1_image

Form pairs of two consecutive elements in the original data sequence and consider them Bitonic sequences. Take two consecutive pairs and apply Bitonic sort on them to make a Bitonic sequence of four-element. Then take two 4-element Bitonic sequences ( here [1, 3, 5, 8] and [9, 7, 4, 2]) and apply Bitonic sort on them to make a Bitonic sequence of 8 elements.

Image of bitonic sequence

So Bitonic sequence we obtained is {1, 3, 5, 8, 9, 7, 4, 2}

Bitonic Sort

Once we have obtained the Bitonic sequence now it’s time to do Bitonic Sort on this sequence.

Steps involved in Bitonic sort :

  1. Create a Bitonic sequence from the original input.
  2. Compare the first element of the first half of the Bitonic sequence to the first element of the second half then the second element of the first half to the second element of the second half and so on. Swap the elements if an element of the first half is greater than an element of the second half. After doing this all elements of the second half will be greater than all elements of the first half.
  3. Now repeat step 2 for n/2 length of Bitonic sequence then n/4 and so on until we get the sorted array.

Image of Bitonic sort

 

C++ Implementation of Bitonic Sort

#include<bits/stdc++.h> 
using namespace std; 

// compare and swap the elements if element of
// first half is greater than second half while 
// merging two bitonic sequences
void compAndSwap(int a[], int i, int j, int order) 
{ 
  if (order == (a[i]>a[j])) 
    swap(a[i],a[j]); 
} 

//function to merge two bitonic sequences 
void bitonicMerge(int a[], int low, int length, int order) 
{ 
    if (length>1) 
  { 
    int k = length/2; 
    for (int i=low; i<low+k; i++) 
      compAndSwap(a, i, i+k, order); 
    bitonicMerge(a, low, k, order); 
    bitonicMerge(a, low+k, k, order); 
  } 
} 

// Bitonic sort function
void bitonicSort(int a[],int low, int length, int order) 
{ 
  if (length>1) 
  { 
    int k = length/2; 

    // sort in ascending order because order is 1 
    bitonicSort(a, low, k, 1); 

    // sort in descending order because order is 0 
    bitonicSort(a, low+k, k, 0); 

    // merge whole sequence in ascending order  
    bitonicMerge(a,low, length, order); 
  } 
} 

// Driver function 
int main() 
{ 
  int a[]= {8, 3, 5, 1, 7, 9, 2, 4}; 
  int n = sizeof(a)/sizeof(a[0]); 

  int incr = 1; // 1 represents ascending order 
  bitonicSort(a, 0, n, incr); 

  printf("Sorted array: "); 
  for (int i=0; i<n; i++) 
    printf("%d ", a[i]); 
  return 0; 
}
Output :Sorted array :  1 2 3 4 5 7 8 9

Leave a Reply

Your email address will not be published. Required fields are marked *