C program to implement Bitonic sort algorithm to sort an array in descending order

In this tutorial, we will learn how to implement Bitonic sort algorithm to sort an array in descending order using C program? By Nidhi Last updated : August 06, 2023

Bitonic merge sort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised by Ken Batcher. The resulting sorting networks consist of O(nlog²(n)) comparators and have a delay of O(log²(n)), where n is the number of items to be sorted. This makes it a popular choice for sorting large numbers of elements on an architecture which itself contains a large number of parallel execution units running in lockstep, such as a typical GPU. Read more at Bitonic sort (Wiki)

Problem statement

Here, we will create an array of integers then we will read array elements from the user and implement a Bitonic sort algorithm to arrange array elements in descending order.

C program to implement Bitonic sort algorithm to sort an array in descending order

The source code to implement the Bitonic sort algorithm is given below. The given program is compiled and executed using GCC compile on UBUNTU 18.04 OS successfully.

// C program to implement Bitonic sort algorithm

#include <stdio.h>

#define MAX 8

int arr[MAX];
int up = 1;
int down = 0;

void Exchange(int* num1, int* num2)
{
    int temp;

    temp = *num1;
    *num1 = *num2;
    *num2 = temp;
}

void compare(int i, int j, int dir)
{
    int t;

    if (dir == (arr[i] > arr[j])) {
        Exchange(&arr[i], &arr[j]);
    }
}

void bitonicmerge(int low, int c, int dir)
{
    int k = 0;
    int i = 0;

    if (c > 1) {
        k = c / 2;
        i = low;
        while (i < low + k) {
            compare(i, i + k, dir);
            i++;
        }

        bitonicmerge(low, k, dir);
        bitonicmerge(low + k, k, dir);
    }
}

void recbitonic(int low, int v, int dir)
{
    int k = 0;

    if (v > 1) {
        k = v / 2;
        recbitonic(low, k, up);
        recbitonic(low + k, k, down);
        bitonicmerge(low, v, dir);
    }
}

int main()
{
    int i = 0;

    printf("Enter array elements:\n");
    while (i < MAX) {
        printf("Element[%d]: ", i);
        scanf("%d", &arr[i]);
        i++;
    }

    recbitonic(0, MAX, 0);

    printf("Sorted Array: \n");
    i = 0;
    while (i < MAX) {
        printf("%d ", arr[i]);
        i++;
    }
    printf("\n");

    return 0;
}

Output

RUN 1:
Enter array elements:
Element[0]: 34
Element[1]: 23
Element[2]: 65
Element[3]: 75
Element[4]: 25
Element[5]: 67
Element[6]: 86
Element[7]: 45
Sorted Array: 
86 75 67 65 45 34 25 23

RUN 2:
Enter array elements:
Element[0]: 10
Element[1]: 20
Element[2]: 30
Element[3]: 55
Element[4]: 15
Element[5]: 17
Element[6]: 70
Element[7]: 85
Sorted Array: 
85 70 55 30 20 17 15 10

Explanation

In the above program, we created five functions Exchange(), compare(), bitonicmerge(), recbitonic(), and main().The Exchange() function is used to swap values of two variable. The compare() function is used to compare array element and perform swapping. The bitonicmerge(), recbitonic() function are used to sort bitonic sequence in descending order.

In the main() function, we read array elements from the user. Then we sorted the elements of the array in descending order using the recbitonic() function and printed the sorted array on the console screen.