shear-sort-pthread-barrier.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
 
#define MATRIX_SIZE 4  // Size of the matrix (example 4x4)
#define NUM_THREADS (MATRIX_SIZE * 2)  // Number of threads for matrix's rows and columns
 
int matrix[MATRIX_SIZE][MATRIX_SIZE];
pthread_barrier_t barrier;
 
// Function to swap two elements
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
// Function executed by each thread to sort a row or column
void *sort_row_or_column(void *arg) {
    int index = *(int*)arg;
    for (int phase = 0; phase < MATRIX_SIZE; phase++) {
        for (int i = 0; i < MATRIX_SIZE - 1; i++) {
            if (index < MATRIX_SIZE) {
                // Sort a row
                if ((phase % 2 == 0 && matrix[index][i] > matrix[index][i + 1]) || 
                    (phase % 2 != 0 && matrix[index][i] < matrix[index][i + 1])) {
                    swap(&matrix[index][i], &matrix[index][i + 1]);
                }
            } else {
                // Sort a column
                int col = index - MATRIX_SIZE;
                if (matrix[i][col] > matrix[i + 1][col]) {
                    swap(&matrix[i][col], &matrix[i + 1][col]);
                }
            }
        }
        // Synchronize all threads at the barrier
        pthread_barrier_wait(&barrier);
    }
 
    pthread_exit(NULL);
}
 
int main() {
    pthread_t threads[NUM_THREADS];
    int thread_args[NUM_THREADS];
    int status;
 
    // Initialize the matrix and barrier
    srand(time(NULL));  // Seed for random numbers
    for (int i = 0; i < MATRIX_SIZE; i++) {
        for (int j = 0; j < MATRIX_SIZE; j++) {
            matrix[i][j] = rand() % 100;  // Random numbers between 0 and 99
        }
    }
    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_row_or_column, (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 matrix
    printf("Sorted Matrix:\n");
    for (int i = 0; i < MATRIX_SIZE; i++) {
        for (int j = 0; j < MATRIX_SIZE; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
 
    // Clean up and exit
    pthread_barrier_destroy(&barrier);
 
    return 0;
}

This program implements the shear sort algorithm for a 2D matrix using pthreads and a barrier.
Each thread is responsible for sorting either a row or a column of the matrix.
The sorting alternates between rows and columns in different phases, with synchronization after each phase using a barrier.

Each thread sorts a row or column of a matrix. The sorting alternates between rows and columns in a way that makes the matrix approach a globally sorted state. The barrier is used to ensure that all threads finish sorting their respective row or column before moving on to the next phase of sorting. This synchronization is essential for the correctness of the shear sort algorithm.

Matrix Initialization: The matrix is filled with random numbers for sorting. This randomness provides a variety of sorting scenarios.

Thread Function (sort_row_or_column): Each thread sorts either a row or a column of the matrix, depending on its index. During even phases, rows are sorted, and in odd phases, columns are sorted. The sorting within each row or column is done in a bubble-sort fashion. If the phase is even, each row is sorted in ascending order. If the phase is odd, each column is sorted, with odd-indexed columns sorted in ascending order and even-indexed columns sorted in descending order. This zig-zag sorting pattern is characteristic of the shear sort algorithm.

Main Function: Initializes the matrix with random values and sets up the barrier. It then creates threads, each assigned to sort a specific row or column. After starting all threads, the main function waits for them to complete their sorting tasks.

Barrier Synchronization: The barrier is crucial for synchronization between sorting phases. It ensures that all threads complete their current phase (either sorting rows or columns) before moving to the next phase. This synchronization is key to the correct functioning of the shear sort algorithm, as it relies on the entire matrix reaching a certain state before switching the sorting direction.

Final Output: After all the sorting phases are complete and the threads have finished execution, the main function prints the sorted matrix. The matrix should be sorted in a 'snakelike' pattern: each row is sorted in ascending order, and each column is sorted in such a way that the elements increase as you move down odd-numbered columns and decrease as you move down even-numbered columns.

This parallel implementation of shear sort effectively utilizes multi-threading to sort a matrix more quickly than a single-threaded approach, especially on multi-core processors.
The algorithm is particularly well-suited for parallel execution due to its distinct row and column sorting phases, making it an excellent choice for parallel sorting of 2D data.