C++ Program To Implement Oddeven Sorting

Odd-Even Sort is a comparison sort algorithm that functions by repeatedly comparing and swapping adjacent elements. It's particularly noted for its efficiency in parallel processing environments.

In this article, you will learn how the Odd-Even Sort algorithm works and how to implement it efficiently in C++.

Problem Statement

Sorting is a fundamental operation in computer science, crucial for organizing data, improving search efficiency, and enabling various algorithms. While many sorting algorithms exist, some, like Odd-Even Sort, offer specific advantages for parallel computing architectures. The challenge is to efficiently arrange a given sequence of elements into a non-decreasing (or non-increasing) order using a method suitable for concurrent execution.

Example

Consider an unsorted array of integers: Input: [5, 2, 8, 1, 9, 4]

After applying Odd-Even Sort, the array will be sorted in ascending order: Output: [1, 2, 4, 5, 8, 9]

Background & Knowledge Prerequisites

To understand and implement Odd-Even Sort, readers should have a basic understanding of:

• C++ Fundamentals: Variables, data types, operators, and control structures (loops, conditionals).
• Arrays: How to declare, initialize, and access elements in a C++ array.
• Functions: Defining and calling functions.
• Comparison Sorting: The general concept of sorting by comparing pairs of elements.

Use Cases or Case Studies

Odd-Even Sort, while not always the fastest for sequential processing, offers unique advantages in specific contexts:

• Parallel Computing Architectures: It's highly suitable for parallel implementation on shared-memory multi-processor systems or sorting networks, as comparisons in each phase (odd or even) can occur independently.
• Fixed-Size Networks: Useful in hardware implementations like sorting networks, where the comparison and swap operations can be hardwired.
• Embedded Systems: For applications where simplicity and a predictable structure for parallel execution are more important than raw sequential speed.
• Educational Tool: A good example for teaching parallel algorithm design due to its clear alternating phases.
• Stable Sorting Requirement: It is a stable sort, meaning that if two elements have equal values, their relative order in the sorted output remains the same as in the input.

Solution Approaches

Odd-Even Sort Implementation

Odd-Even Sort works by repeatedly performing two phases: an odd phase and an even phase. In the odd phase, it compares and swaps adjacent elements at odd indices (1st and 2nd, 3rd and 4th, etc.). In the even phase, it compares and swaps adjacent elements at even indices (2nd and 3rd, 4th and 5th, etc.). These phases alternate until the array is sorted.

// Odd-Even Sort Implementation
#include <iostream>
#include <vector>
#include <algorithm> // Required for std::swap

void oddEvenSort(std::vector<int>& arr) {
    int n = arr.size();
    bool isSorted = false; // Flag to check if the array is sorted

    while (!isSorted) {
        isSorted = true; // Assume array is sorted until a swap occurs

        // Odd Phase: Compare and swap elements at odd indices (1, 3, 5...)
        for (int i = 1; i <= n - 2; i += 2) {
            if (arr[i] > arr[i+1]) {
                std::swap(arr[i], arr[i+1]);
                isSorted = false; // A swap occurred, so array might not be sorted yet
            }
        }

        // Even Phase: Compare and swap elements at even indices (0, 2, 4...)
        for (int i = 0; i <= n - 2; i += 2) {
            if (arr[i] > arr[i+1]) {
                std::swap(arr[i], arr[i+1]);
                isSorted = false; // A swap occurred
            }
        }
    }
}

// Function to print the array
void printArray(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

int main() {
    // Step 1: Initialize an unsorted vector
    std::vector<int> arr = {5, 2, 8, 1, 9, 4, 3, 7, 6};
    std::cout << "Original array: ";
    printArray(arr);

    // Step 2: Apply Odd-Even Sort
    oddEvenSort(arr);

    // Step 3: Print the sorted array
    std::cout << "Sorted array:   ";
    printArray(arr);

    // Test with another array
    std::vector<int> arr2 = {10, -5, 0, 20, 15};
    std::cout << "Original array 2: ";
    printArray(arr2);
    oddEvenSort(arr2);
    std::cout << "Sorted array 2:   ";
    printArray(arr2);

    return 0;
}

Run

Sample Output

Original array: 5 2 8 1 9 4 3 7 6 
Sorted array:   1 2 3 4 5 6 7 8 9 
Original array 2: 10 -5 0 20 15 
Sorted array 2:   -5 0 10 15 20

Stepwise Explanation

1. oddEvenSort Function:

• Takes a std::vector& arr as input, allowing the function to modify the original vector.
• n stores the size of the array.
• isSorted is a boolean flag, initialized to false. The algorithm continues in a while (!isSorted) loop until no swaps occur in an entire pass (both odd and even phases), indicating the array is sorted.

1. Odd Phase Loop:

• The first for loop iterates through odd indices (i = 1, 3, 5, ...).
• It compares arr[i] with its adjacent element arr[i+1].
• If arr[i] > arr[i+1], they are swapped using std::swap.
• If a swap occurs, isSorted is set to false, because the array is not yet fully sorted.

1. Even Phase Loop:

• The second for loop iterates through even indices (i = 0, 2, 4, ...).
• It compares arr[i] with its adjacent element arr[i+1].
• If arr[i] > arr[i+1], they are swapped.
• Again, if a swap occurs, isSorted is set to false.

1. main Function:

• An initial std::vector named arr is created with unsorted elements.
• The printArray utility function displays the original array.
• oddEvenSort(arr) is called to sort the vector.
• Finally, the sorted array is printed.
• A second test case is included to demonstrate its robustness.

Conclusion

Odd-Even Sort is a fascinating comparison sort that, despite its O(n^2) time complexity in the worst case (similar to Bubble Sort) for sequential processing, offers significant advantages in parallel computing due to its structured and independent comparison phases. Its simplicity and natural fit for sorting networks make it a valuable algorithm in specific architectural contexts.

Summary

• Odd-Even Sort is a comparison-based sorting algorithm.
• It operates in alternating odd and even phases, comparing and swapping adjacent elements.
• During the odd phase, elements at (i, i+1) are compared for odd i.
• During the even phase, elements at (i, i+1) are compared for even i.
• The algorithm repeats these phases until no swaps occur in a complete pass, indicating the array is sorted.
• It is particularly well-suited for parallel processing environments and hardware sorting networks.
• Odd-Even Sort is a stable sorting algorithm.