Bogosort multithread

mail@pastecode.io avatar
unknown
c_cpp
2 months ago
4.1 kB
2
Indexable
Never
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <time.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;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t condition = PTHREAD_COND_INITIALIZER;

// 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;

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

   while (1) {
       pthread_mutex_lock(&mutex);
       if (arraySorted) {
           pthread_mutex_unlock(&mutex);
           break;
       }
       shuffleArray(info->array, info->arraySize);
       info->shuffleCount++;
       if (isSorted(info->array, info->arraySize)) {
           arraySorted = 1;
           pthread_cond_broadcast(&condition);
       }
       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;

   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;
   }

   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");

   ThreadInfo* threadInfos = malloc(numThreads * sizeof(ThreadInfo));
   pthread_t* threads = malloc(numThreads * sizeof(pthread_t));

   struct timespec startTime, endTime;
   clock_gettime(CLOCK_MONOTONIC, &startTime);

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

   pthread_mutex_lock(&mutex);
   while (!arraySorted) {
       pthread_cond_wait(&condition, &mutex);
   }
   pthread_mutex_unlock(&mutex);

   clock_gettime(CLOCK_MONOTONIC, &endTime);

   printf("Sorted Array: ");
   for (int i = 0; i < arraySize; i++) {
       printf("%d ", originalArray[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);
   }

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

   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);

   return 0;
}
Leave a Comment