Multithreaded Bogosort in C

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <time.h>
#include <string.h>

#define MAX_ARRAY_SIZE 1000
#define MAX_THREADS 32

// Struct to hold thread information
typedef struct {
    int threadId;
    int* array;
    int arraySize;
    long long shuffleCount;
    double shuffleRate;
} ThreadInfo;

// Global variables
int originalArray[MAX_ARRAY_SIZE];
int numThreads;
int arraySorted = 0;
int globalArrayUpdated = 0;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t condition = PTHREAD_COND_INITIALIZER;
pthread_cond_t updatedCondition = PTHREAD_COND_INITIALIZER;
int* sortedArray = NULL;

// Function to swap two elements in an array
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to shuffle an array
void shuffleArray(int* array, int size) {
    for (int i = size - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        swap(&array[i], &array[j]);
    }
}

// Function to check if an array is sorted
int isSorted(int* array, int size) {
    for (int i = 0; i < size - 1; i++) {
        if (array[i] > array[i + 1]) {
            return 0;
        }
    }
    return 1;
}

// Thread function to perform Bogosort
void* bogosort(void* arg) {
    ThreadInfo* info = (ThreadInfo*)arg;
    int* localArray = malloc(info->arraySize * sizeof(int));
    memcpy(localArray, info->array, info->arraySize * sizeof(int));

    struct timespec start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);

    while (!globalArrayUpdated) {
        shuffleArray(localArray, info->arraySize);
        info->shuffleCount++;

        if (isSorted(localArray, info->arraySize)) {
            pthread_mutex_lock(&mutex);
            if (!arraySorted) {
                arraySorted = 1;
                sortedArray = malloc(info->arraySize * sizeof(int));
                memcpy(sortedArray, localArray, info->arraySize * sizeof(int));
                globalArrayUpdated = 1;
                pthread_cond_broadcast(&condition);
                pthread_cond_broadcast(&updatedCondition);
            }
            pthread_mutex_unlock(&mutex);
        }
    }

    clock_gettime(CLOCK_MONOTONIC, &end);
    double elapsed = (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1000000000.0;
    info->shuffleRate = info->shuffleCount / elapsed;

    free(localArray);
    pthread_exit(NULL);
}

int main(int argc, char* argv[]) {
    if (argc != 3) {
        printf("Usage: %s <array_size> <num_threads>\n", argv[0]);
        return 1;
    }

    int arraySize = atoi(argv[1]);
    numThreads = atoi(argv[2]);

    if (arraySize > MAX_ARRAY_SIZE || numThreads > MAX_THREADS) {
        printf("Array size or number of threads exceeds the maximum limit.\n");
        return 1;
    }

    // Initialize original array with random numbers
    srand(time(NULL));
    for (int i = 0; i < arraySize; i++) {
        originalArray[i] = rand() % 1000 + 1;
    }

    printf("Original Array: ");
    for (int i = 0; i < arraySize; i++) {
        printf("%d ", originalArray[i]);
    }
    printf("\n");

    // Create thread information structs and threads
    ThreadInfo* threadInfos = malloc(numThreads * sizeof(ThreadInfo));
    pthread_t* threads = malloc(numThreads * sizeof(pthread_t));

    // Capture the start time
    struct timespec startTime, endTime;
    clock_gettime(CLOCK_MONOTONIC, &startTime);

    for (int i = 0; i < numThreads; i++) {
        threadInfos[i].threadId = i;
        threadInfos[i].array = malloc(arraySize * sizeof(int));
        memcpy(threadInfos[i].array, originalArray, arraySize * sizeof(int));
        threadInfos[i].arraySize = arraySize;
        threadInfos[i].shuffleCount = 0;
        pthread_create(&threads[i], NULL, bogosort, &threadInfos[i]);
    }

    // Wait for a thread to signal that the array is sorted and updated
    pthread_mutex_lock(&mutex);
    while (!arraySorted) {
        pthread_cond_wait(&condition, &mutex);
    }
    while (!globalArrayUpdated) {
        pthread_cond_wait(&updatedCondition, &mutex);
    }
    pthread_mutex_unlock(&mutex);

    // Capture the end time
    clock_gettime(CLOCK_MONOTONIC, &endTime);

    // Print sorted array and other information
    printf("Sorted Array: ");
    for (int i = 0; i < arraySize; i++) {
        printf("%d ", sortedArray[i]);
    }
    printf("\n");

    long long totalShuffleCount = 0;
    double totalShuffleRate = 0.0;

    for (int i = 0; i < numThreads; i++) {
        pthread_join(threads[i], NULL);
        totalShuffleCount += threadInfos[i].shuffleCount;
        totalShuffleRate += threadInfos[i].shuffleRate;
        printf("Thread %d: Shuffle Count = %lld, Shuffle Rate = %.2f shuffles/sec\n",
               i, threadInfos[i].shuffleCount, threadInfos[i].shuffleRate);
        free(threadInfos[i].array);
    }

    printf("Total Shuffle Count: %lld\n", totalShuffleCount);
    printf("Total Shuffle Rate: %.2f shuffles/sec\n", totalShuffleRate);

    // Calculate and print the time taken to sort the array
    double elapsedTime = (endTime.tv_sec - startTime.tv_sec) + (endTime.tv_nsec - startTime.tv_nsec) / 1000000000.0;
    printf("Time taken to sort the array: %.2f seconds\n", elapsedTime);

    free(threadInfos);
    free(threads);
    free(sortedArray);

    return 0;
}