C Program To Implement Bitonic Sorting

Bitonic Sort is an efficient comparison-based sorting algorithm, particularly well-suited for parallel processing architectures. In this article, you will learn how to implement Bitonic Sort in C, understand its underlying principles, and explore its practical applications.

Problem Statement

Sorting large datasets efficiently is a fundamental challenge in computer science, especially as systems move towards multi-core processors and parallel computing. Traditional sorting algorithms often have sequential bottlenecks. The problem is to develop a sorting algorithm that can leverage parallel processing effectively, providing predictable performance for fixed-size inputs or specialized hardware.

Example

Consider an unsorted array of numbers: [3, 7, 4, 8, 6, 2, 1, 5]. After applying Bitonic Sort in ascending order, the array will be sorted as: [1, 2, 3, 4, 5, 6, 7, 8].

Background & Knowledge Prerequisites

To understand Bitonic Sort, readers should be familiar with:

• C Language Basics: Variables, arrays, functions, loops, and conditional statements.
• Recursion: Understanding how functions call themselves.
• Arrays: Manipulating elements within an array.
• Basic Sorting Concepts: Comparison and swapping of elements.
• Bitonic Sequence: A sequence of numbers that is first monotonically increasing and then monotonically decreasing, or vice-versa. For example, [1, 2, 4, 5, 3, 2, 1] is a bitonic sequence. A circularly shifted version is also bitonic, e.g., [5, 3, 2, 1, 1, 2, 4].

Use Cases or Case Studies

Bitonic Sort is particularly useful in scenarios requiring parallel processing and predictable performance:

• Parallel Computing: Its structure allows for efficient implementation on parallel processors like GPUs or custom hardware, where many comparisons can happen concurrently.
• Network Routing: Used in designing efficient switching networks where data packets need to be routed and ordered.
• Hardware Sorting Circuits: Due to its regular, data-independent comparison network, Bitonic Sort is a strong candidate for implementation in custom hardware sorting circuits (e.g., ASICs or FPGAs).
• Fixed-Size Data Sorting: Ideal for applications where the size of data to be sorted is known in advance and remains constant, optimizing resource allocation.
• Memory-Constrained Environments: Can be adapted for sorting large datasets that do not fit into main memory by breaking them into smaller, manageable bitonic sequences.

Solution Approaches

Recursive Bitonic Sort Implementation

This approach utilizes a recursive divide-and-conquer strategy to build and merge bitonic sequences until the entire array is sorted.

One-line summary: The algorithm recursively sorts sub-sequences in alternating directions (ascending/descending) to form bitonic sequences, then repeatedly merges these bitonic sequences into a single sorted sequence.

Code example:

// Bitonic Sort Implementation
#include <stdio.h>
#include <stdlib.h> // For malloc and free, though not strictly needed for this fixed-size example

// Function to swap two elements
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to compare and swap elements based on direction
// dir = 1 for ascending, 0 for descending
void compareAndSwap(int arr[], int i, int j, int dir) {
    if ((arr[i] > arr[j] && dir == 1) || (arr[i] < arr[j] && dir == 0)) {
        swap(&arr[i], &arr[j]);
    }
}

// Function to merge a bitonic sequence
// It splits the sequence into two halves and recursively merges them
// 'dir' indicates the overall sorting direction (1 for ascending, 0 for descending)
void bitonicMerge(int arr[], int low, int count, int dir) {
    if (count > 1) {
        int k = count / 2;
        // Compare elements in the first half with elements in the second half
        for (int i = low; i < low + k; i++) {
            compareAndSwap(arr, i, i + k, dir);
        }
        // Recursively merge the two halves
        bitonicMerge(arr, low, k, dir);
        bitonicMerge(arr, low + k, k, dir);
    }
}

// Function to implement bitonic sort
// It recursively sorts two halves of the array in opposite directions
// and then merges them using bitonicMerge
// 'dir' indicates the desired sorting direction for this sub-sequence
void bitonicSort(int arr[], int low, int count, int dir) {
    if (count > 1) {
        int k = count / 2;
        // Sort first half in ascending order
        bitonicSort(arr, low, k, 1);
        // Sort second half in descending order
        bitonicSort(arr, low + k, k, 0);
        // Merge the entire bitonic sequence in the desired 'dir'
        bitonicMerge(arr, low, count, dir);
    }
}

// Helper function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");
}

int main() {
    // Step 1: Define an array to be sorted.
    // The size of the array must be a power of 2 for this implementation.
    int arr[] = {3, 7, 4, 8, 6, 2, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    // Step 2: Call the bitonicSort function to sort the array in ascending order (dir = 1).
    bitonicSort(arr, 0, n, 1);

    printf("Sorted array:   ");
    printArray(arr, n);

    return 0;
}

Run

Sample output:

Original array: 3 7 4 8 6 2 1 5 
Sorted array:   1 2 3 4 5 6 7 8

Stepwise explanation:

1. swap(int* a, int* b): A utility function to exchange the values of two integers.
2. compareAndSwap(int arr[], int i, int j, int dir): This function takes two indices i and j, and a dir (direction). If dir is 1 (ascending), it ensures arr[i] <= arr[j]. If dir is 0 (descending), it ensures arr[i] >= arr[j]. If the condition is violated, the elements are swapped. This is the fundamental comparison operation of the algorithm.
3. bitonicMerge(int arr[], int low, int count, int dir): This function takes a bitonic sequence (defined by low starting index and count elements) and merges it into a sorted sequence in the specified dir.

• It first performs compareAndSwap operations between elements in the first half and corresponding elements in the second half (arr[i] with arr[i + k]). This step ensures that the two halves, when viewed independently, become bitonic themselves and that elements across the middle are ordered correctly relative to dir.
• It then recursively calls bitonicMerge on the first half and the second half. This recursive merging eventually sorts the entire bitonic sequence.

1. bitonicSort(int arr[], int low, int count, int dir): This is the main recursive function that constructs the bitonic sequences.

• It divides the current sequence (low to low + count - 1) into two halves.
• It recursively calls bitonicSort on the *first half* to sort it in *ascending* order (dir = 1).
• It recursively calls bitonicSort on the *second half* to sort it in *descending* order (dir = 0).
• After these two recursive calls, the entire sequence (from low to low + count - 1) becomes a bitonic sequence.
• Finally, it calls bitonicMerge on this newly formed bitonic sequence to sort it in the overall desired dir.

1. main() function:

• An array arr is initialized. Its size n must be a power of 2 for this standard recursive implementation.
• The original array is printed.
• bitonicSort is called with low = 0, count = n, and dir = 1 (for ascending sort).
• The sorted array is printed.

This recursive structure ensures that at each step, smaller bitonic sequences are formed and merged until the entire array becomes a sorted sequence.

Conclusion

Bitonic Sort offers a robust and elegant solution for sorting, especially in environments benefiting from parallel execution. Its inherent structure, relying on a fixed comparison network, makes it highly amenable to hardware implementations and parallel programming models. While its $O(N \log^2 N)$ time complexity might be higher than some comparison sorts in a purely sequential model, its ability to execute $N \log^2 N$ comparisons in parallel $O(\log^2 N)$ time gives it a significant advantage for specific architectures.

Summary

• Bitonic Sort is a parallel sorting algorithm effective for fixed-size data and parallel architectures.
• It operates by recursively building and merging "bitonic sequences," which are sequences that increase then decrease (or vice-versa).
• The algorithm's core operations are compareAndSwap and bitonicMerge, which leverage a divide-and-conquer approach.
• It is particularly useful in parallel computing, GPU programming, network routing, and hardware sorting circuits.
• The standard implementation requires the input array size to be a power of 2.