C Program To Implement Oddeven Sorting

Odd-Even Sort is a parallel sorting algorithm that efficiently arranges elements by repeatedly comparing and swapping adjacent pairs. In this article, you will learn how to implement the Odd-Even Sort algorithm in C, understand its mechanics, and see it in action.

Problem Statement

Sorting an array of numbers is a fundamental task in computer science, essential for data organization and efficient retrieval. While many sorting algorithms exist, some are better suited for specific architectures, such as parallel processing environments. The challenge is to find an algorithm that can effectively sort data, especially when considering parallel execution where comparisons and swaps can occur simultaneously.

Example

Consider an unsorted array: [5, 2, 4, 1, 3]

After applying Odd-Even Sort, the array should become: [1, 2, 3, 4, 5]

Background & Knowledge Prerequisites

To understand and implement Odd-Even Sort, you should have a basic grasp of:

• C Programming Basics: Variables, data types, operators, basic I/O.
• Arrays: Declaring, initializing, and accessing elements.
• Loops: for and while loops for iteration.
• Conditional Statements: if statements for comparisons.
• Functions: Defining and calling functions (e.g., for swapping elements).
• Comparison Sorting: The general concept of sorting by comparing pairs of elements.

Use Cases or Case Studies

Odd-Even Sort, while not optimal for single-processor performance compared to algorithms like QuickSort or MergeSort, finds its niche in specific scenarios:

• Parallel Processing Architectures: Its design allows for comparisons and swaps of independent pairs to occur concurrently, making it suitable for hardware with many processing units.
• Systolic Arrays: It can be implemented efficiently on fixed-size networks of processors, where data flows through processing elements in a pipeline fashion.
• Hardware Sorting Networks: Its regular structure is advantageous for designing custom hardware for sorting operations.
• Fixed-Size Networks: Useful in situations where the data is distributed across a fixed number of processing nodes that can only communicate with their immediate neighbors.

Solution Approaches

The core idea of Odd-Even Sort is to perform comparisons and swaps in two phases: an "odd phase" and an "even phase." These phases are repeated until the array is sorted.

Odd-Even Sort Implementation

This approach involves iterating through the array in two alternating passes: one comparing odd-indexed pairs (1-2, 3-4, etc.) and another comparing even-indexed pairs (0-1, 2-3, etc.).

One-line summary: Repeatedly sorts elements by comparing and swapping adjacent pairs in alternating odd and even phases until no more swaps are needed.

Code Example:

// Odd-Even Sort Implementation
#include <stdio.h>
#include <stdbool.h> // For boolean type

// Function to swap two integers
void swap(int* xp, int* yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

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

// Function to implement Odd-Even Sort
void oddEvenSort(int arr[], int n) {
    bool isSorted = false; // Initially assume array is not sorted

    // Step 1: Loop until no swaps are made in an entire pass
    while (!isSorted) {
        isSorted = true; // Assume sorted for this pass, if no swaps, it's true

        // Step 2: Perform Odd Phase (compare and swap odd-indexed pairs)
        // Compare (arr[1], arr[2]), (arr[3], arr[4]), etc.
        for (int i = 1; i <= n - 2; i += 2) {
            if (arr[i] > arr[i+1]) {
                swap(&arr[i], &arr[i+1]);
                isSorted = false; // A swap occurred, so array is not fully sorted yet
            }
        }

        // Step 3: Perform Even Phase (compare and swap even-indexed pairs)
        // Compare (arr[0], arr[1]), (arr[2], arr[3]), etc.
        for (int i = 0; i <= n - 2; i += 2) {
            if (arr[i] > arr[i+1]) {
                swap(&arr[i], &arr[i+1]);
                isSorted = false; // A swap occurred, so array is not fully sorted yet
            }
        }
    }
}

int main() {
    // Step 1: Define an array to be sorted
    int arr[] = {5, 2, 4, 1, 3, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

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

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

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

    return 0;
}

Run

Sample Output:

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

Stepwise Explanation:

1. swap Function: A utility function swap(int* xp, int* yp) is created to exchange the values of two integers. This is a common helper in sorting algorithms.
2. printArray Function: Another utility function to display the contents of an array, useful for visualizing the sorting process.
3. oddEvenSort Function Initialization:

• It takes an integer array arr and its size n as input.
• A boolean variable isSorted is initialized to false. This flag helps determine when the array is fully sorted.

1. Main Sorting Loop:

• The while (!isSorted) loop continues as long as the array is not fully sorted.
• At the beginning of each iteration (pass), isSorted is set to true, assuming that no swaps will be needed in the current pass. If any swap occurs, isSorted is reset to false, signaling that another pass is required.

1. Odd Phase:

• The for loop for (int i = 1; i <= n - 2; i += 2) iterates through odd indices (1, 3, 5, ...).
• It compares arr[i] with arr[i+1] (e.g., arr[1] with arr[2], arr[3] with arr[4]).
• If arr[i] is greater than arr[i+1], they are swapped using the swap function, and isSorted is set to false.

1. Even Phase:

• The for loop for (int i = 0; i <= n - 2; i += 2) iterates through even indices (0, 2, 4, ...).
• It compares arr[i] with arr[i+1] (e.g., arr[0] with arr[1], arr[2] with arr[3]).
• If arr[i] is greater than arr[i+1], they are swapped, and isSorted is set to false.

1. Termination: The while loop terminates only when an entire pass (both odd and even phases) completes without performing any swaps, indicating that the array is finally sorted.
2. main Function: Initializes a sample array, prints its original state, calls oddEvenSort, and then prints the sorted array.

Conclusion

Odd-Even Sort provides a fascinating approach to sorting, particularly valuable in contexts where parallel execution is feasible. Its structured two-phase comparison mechanism ensures that elements progressively move to their correct positions, leading to a fully sorted array. While it may not be the fastest for sequential processing, its design makes it an interesting candidate for specialized hardware and parallel computing environments.

Summary

• Odd-Even Sort is a parallel sorting algorithm that operates in alternating odd and even phases.
• Odd Phase: Compares and swaps elements at odd-indexed positions with their next element (arr[i] and arr[i+1] where i is odd).
• Even Phase: Compares and swaps elements at even-indexed positions with their next element (arr[i] and arr[i+1] where i is even).
• The algorithm repeatedly performs these phases until an entire pass occurs without any swaps, signifying that the array is sorted.
• Its structured nature makes it suitable for implementation in parallel architectures and hardware sorting networks.