Odd Even Transposition Sort (Parallel Bubble Sort) Using Pthreads and Barrier

oetc-pthread-barrier.c

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
 
#define NUM_THREADS 4  // Number of threads (should be even)
#define ARRAY_SIZE 8   // Size of the array
 
int array[ARRAY_SIZE];
pthread_barrier_t barrier;
 
// Function to swap two array elements
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
// Function executed by each thread
void *sort(void *arg) {
    int thread_part = *(int*)arg;
    for (int phase = 0; phase < ARRAY_SIZE; phase++) {
        // Determine pairs for this phase
        int index = thread_part * 2 + (phase % 2);
 
        // Compare and swap if needed
        if (index < ARRAY_SIZE - 1 && array[index] > array[index + 1]) {
            swap(&array[index], &array[index + 1]);
        }
 
        // Wait for all threads to finish this phase
        pthread_barrier_wait(&barrier);
    }
 
    pthread_exit(NULL);
}
 
int main() {
    pthread_t threads[NUM_THREADS];
    int thread_args[NUM_THREADS];
    int status;
 
    // Initialize array with random values
    for (int i = 0; i < ARRAY_SIZE; i++) {
        array[i] = rand() % 100;  // Random numbers between 0 and 99
    }
 
    // Initialize barrier
    pthread_barrier_init(&barrier, NULL, NUM_THREADS);
 
    // Create threads for sorting
    for (int i = 0; i < NUM_THREADS; i++) {
        thread_args[i] = i;
        status = pthread_create(&threads[i], NULL, sort, (void *)&thread_args[i]);
 
        if (status != 0) {
            printf("ERROR; return code from pthread_create() is %d\n", status);
            exit(-1);
        }
    }
 
    // Wait for all threads to complete
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }
 
    // Print the sorted array
    printf("Sorted Array: ");
    for (int i = 0; i < ARRAY_SIZE; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
 
    // Clean up and exit
    pthread_barrier_destroy(&barrier);
 
    return 0;
}

The program parallelize the odd-even transposition sort algorithm using pthreads and a barrier. In this sorting algorithm, threads work in pairs on adjacent elements of the array, comparing and swapping them if they are in the wrong order.
The use of a barrier synchronizes threads between each phase of comparisons, ensuring that all comparisons and swaps for a phase are completed before moving to the next phase.

Array Initialization: The array is initialized with random values for sorting.

Thread Function (sort): Each thread works on pairs of elements. The pairs each thread works on depend on the current phase (odd or even). The function includes a swap operation if elements are out of order and synchronizes threads using a barrier at the end of each phase.

Main Function: Sets up the barrier, creates threads, and starts the sorting process. Once sorting is complete, it joins all threads and prints the sorted array.

Barrier Synchronization: The barrier ensures that all threads complete their part of the sorting phase before moving to the next phase, maintaining the correctness of the sorting algorithm.

This parallel implementation can significantly speed up the sorting process on large arrays and multi-core processors by leveraging the power of concurrent execution.

The critical aspect of this parallel algorithm is ensuring that all threads have completed their part of the sorting in a phase before moving on to the next phase, which is accomplished using the barrier.