Bogosort multithread
unknown
c_cpp
a year ago
4.1 kB
5
Indexable
#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; }
Editor is loading...
Leave a Comment