C++ Program To Implement Bitonic Sorting

In this article, you will learn how to implement the bitonic sort algorithm in C++. You will explore its structure, understand its recursive components, and see a practical example of its application.

Problem Statement

Sorting data efficiently is a fundamental task in computer science. While many general-purpose sorting algorithms exist, some specialized algorithms are particularly well-suited for specific architectures, such as parallel processing environments. Bitonic sort is one such algorithm, designed for parallel implementation and often used in hardware sorting networks. The problem is to arrange a sequence of elements into a sorted order using a bitonic sorting network principle.

Example

Consider an unsorted array of numbers: [3, 7, 4, 8, 6, 2, 1, 5]. After applying the bitonic sort algorithm in ascending order, the array will become: [1, 2, 3, 4, 5, 6, 7, 8].

Background & Knowledge Prerequisites

To understand and implement bitonic sort, a basic understanding of the following concepts is helpful:

• C++ Fundamentals: Variables, data types, functions, control flow (if-else, loops).
• Arrays/Vectors: How to declare, initialize, and manipulate dynamic arrays (std::vector).
• Recursion: The concept of functions calling themselves.
• Divide and Conquer: The strategy of breaking a problem into smaller subproblems.

It's also important to note that bitonic sort typically works most efficiently when the number of elements N is a power of two. For sequences not satisfying this, padding with sentinel values might be required.

Use Cases

Bitonic sort, while not always the fastest for sequential processing, offers unique advantages in specific scenarios:

• Parallel Processing: Its structure makes it highly amenable to parallel execution, as many comparisons can be performed simultaneously.
• Hardware Sorting Networks: It forms the basis for designing sorting circuits in hardware due to its fixed comparison patterns, which are independent of the input data.
• GPU Computing: The algorithm can be efficiently mapped to GPU architectures where massive parallelism is available.
• Fixed-Topology Networks: Useful in sorting within networks where data movement is restricted to a predefined structure.

Solution Approaches

Bitonic sort is a comparison network sort that relies on the concept of a "bitonic sequence." A bitonic sequence is a sequence that first monotonically increases and then monotonically decreases, or vice versa. For example, [1, 3, 4, 8, 7, 6, 2] is a bitonic sequence.

The algorithm works in two main phases:

1. Building Bitonic Sequences: Recursively sort smaller segments of the array into bitonic sequences.
2. Merging Bitonic Sequences: Merge these bitonic sequences into a fully sorted sequence.

Approach 1: Recursive Bitonic Sort Algorithm

This approach involves three main helper functions: compareAndSwap, bitonicMerge, and the main bitonicSort function.

One-line summary: Recursively divides the array, sorts halves into opposing bitonic sequences, and then merges them into a single sorted bitonic sequence in the desired direction.

Code Example:

// Bitonic Sort Implementation
#include <iostream>
#include <vector>
#include <algorithm> // For std::swap

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

// Function to merge a bitonic sequence in a specified direction
// low: starting index of the sub-array
// cnt: number of elements in the sub-array
// dir: 1 for ascending merge, 0 for descending merge
void bitonicMerge(std::vector<int>& arr, int low, int cnt, int dir) {
    if (cnt > 1) {
        int k = cnt / 2; // Half the current segment size
        // Compare elements k distance apart within the segment
        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
// low: starting index of the sub-array
// cnt: number of elements in the sub-array
// dir: 1 for ascending sort, 0 for descending sort
void bitonicSort(std::vector<int>& arr, int low, int cnt, int dir) {
    if (cnt > 1) {
        int k = cnt / 2;
        // Step 1: Recursively sort the first half in ascending order
        bitonicSort(arr, low, k, 1);
        // Step 2: Recursively sort the second half in descending order
        bitonicSort(arr, low + k, k, 0);
        // Step 3: Merge the entire sequence in the specified direction
        bitonicMerge(arr, low, cnt, dir);
    }
}

// Helper function to call bitonicSort for the entire array
// N: total number of elements in the array
// dir: 1 for ascending sort, 0 for descending sort
void sort(std::vector<int>& arr, int N, int dir) {
    bitonicSort(arr, 0, N, dir);
}

int main() {
    std::vector<int> arr = {3, 7, 4, 8, 6, 2, 1, 5};
    int N = arr.size();

    std::cout << "Original array: ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Sort in ascending order (dir = 1)
    sort(arr, N, 1);

    std::cout << "Sorted array (ascending): ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Re-initialize array for descending sort example
    arr = {3, 7, 4, 8, 6, 2, 1, 5};
    std::cout << "Original array (for descending sort): ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Sort in descending order (dir = 0)
    sort(arr, N, 0);

    std::cout << "Sorted array (descending): ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

Sample Output:

Original array: 3 7 4 8 6 2 1 5 
Sorted array (ascending): 1 2 3 4 5 6 7 8 
Original array (for descending sort): 3 7 4 8 6 2 1 5 
Sorted array (descending): 8 7 6 5 4 3 2 1

Stepwise Explanation:

1. compareAndSwap(std::vector& arr, int i, int j, int dir):

• This is the most basic building block. It takes two indices i and j and a direction dir.
• If dir is 1 (ascending), it ensures arr[i] <= arr[j]. If arr[i] is greater, they are swapped.
• If dir is 0 (descending), it ensures arr[i] >= arr[j]. If arr[i] is smaller, they are swapped.

1. bitonicMerge(std::vector& arr, int low, int cnt, int dir):

• This function takes a bitonic sequence (of length cnt starting at low) and merges it into a sorted sequence in the specified dir.
• It first divides the bitonic sequence into two halves (k = cnt / 2).
• It then iterates through the first half and compares arr[i] with arr[i + k], swapping them if they are in the wrong order according to dir using compareAndSwap. This step ensures that after these comparisons, the sequence becomes "more sorted."
• Finally, it recursively calls bitonicMerge on the first half and the second half, both in the *same* dir, to complete the merge.

1. bitonicSort(std::vector& arr, int low, int cnt, int dir):

• This is the core recursive sorting function.
• It divides the segment (of length cnt starting at low) into two halves.
• It recursively calls bitonicSort on the first half (low to low + k - 1) to sort it in ascending order (dir = 1). This creates an ascending bitonic sequence.
• It recursively calls bitonicSort on the second half (low + k to low + cnt - 1) to sort it in descending order (dir = 0). This creates a descending bitonic sequence.
• After these two recursive calls, the entire segment (from low to low + cnt - 1) becomes a bitonic sequence.
• Finally, it calls bitonicMerge on this newly formed bitonic sequence to merge it into a fully sorted sequence in the originally specified dir.

The main function demonstrates how to use the sort helper function (which wraps bitonicSort) to sort an example array in both ascending and descending order.

Conclusion

Bitonic sort is a powerful comparison-based sorting algorithm, particularly valuable for its parallelizability and suitability for hardware implementations. By recursively building and merging bitonic sequences, it achieves sorting in a highly structured manner. While its time complexity is O(N log² N) which is slightly higher than O(N log N) for quicksort or mergesort in sequential execution, its parallel nature often makes it faster in multi-core or GPU environments.

Summary

• Bitonic sort organizes data using a "divide and conquer" approach.
• It builds bitonic sequences (monotonically increasing then decreasing, or vice versa) and then merges them.
• The algorithm is recursive, with helper functions for comparison and merging.
• It's highly efficient for parallel processing and hardware sorting networks.
• Typically performs best when the input size N is a power of two.
• Implemented using compareAndSwap, bitonicMerge, and bitonicSort functions.