Skip to content
Snippets Groups Projects

Bucket sort implementation in C

Open Elvan Owen requested to merge elvanowen/OpenMPI_2:master into master
Compare and
+ 143
0
Preferences
Compare changes
bucket_sort.c 0 → 100644
+ 143
0
 
#include <stdio.h>
 
#include <stdlib.h>
 
#include <time.h>
 
#include <mpi.h>
 
#include <assert.h>
 
 
int *create_rand_nums(int num_elements) {
 
 
int *rand_nums = (int *)malloc(sizeof(int) * num_elements);
 
assert(rand_nums != NULL);
 
 
int i;
 
for (i = 0; i < num_elements; i++) {
 
rand_nums[i] = (rand() / (int)RAND_MAX);
 
}
 
 
return rand_nums;
 
}
 
 
void insertion_sort(int* bucket, int bucket_size){
 
int i,j,temp;
 
 
for(i=1;i<bucket_size;i++){
 
temp=bucket[i];
 
j=i-1;
 
 
while((temp<bucket[j])&&(j>=0)){
 
bucket[j+1]=bucket[j];
 
j=j-1;
 
}
 
 
bucket[j+1]=temp;
 
}
 
}
 
 
int main(int argc,char* argv[]) {
 
if (argc != 3) {
 
fprintf(stderr, "Usage: bucket_sort <total_numbers>\n");
 
exit(1);
 
}
 
 
int num_elements = atoi(argv[1]);
 
 
int num_tasks, world_rank;
 
double total_sort_time = 0.0, total_distribution_time = 0.0;
 
 
MPI_Status stat;
 
MPI_Init(&argc,&argv);
 
MPI_Comm_size(MPI_COMM_WORLD, &num_tasks);
 
MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
 
 
int* rand_nums = create_rand_nums(num_elements);
 
int *sorted_numbers = (int*)malloc(sizeof(int) * num_elements);
 
 
if (world_rank == 0) {
 
int max = rand_nums[0];
 
 
int i = 0;
 
for(i=0; i < num_elements; i++) {
 
if(rand_nums[i] > max) max = rand_nums[i];
 
}
 
 
int* num_elements_per_proc = (int *)malloc(sizeof(int) * num_tasks);
 
 
i = 0;
 
for (;i<num_tasks;i++) num_elements_per_proc[i] = 0;
 
 
int step = max/(num_tasks-1);
 
int boundary = step;
 
int bucket_no = 1;
 
 
for(; boundary <= max; boundary += step, ++bucket_no) {
 
i = 0;
 
for(; i < num_elements; i++) {
 
if(rand_nums[i] > boundary - step && rand_nums[i] <= boundary) {
 
num_elements_per_proc[bucket_no]++;
 
}
 
}
 
}
 
 
total_distribution_time -= MPI_Wtime();
 
 
i = 1;
 
for(; i<num_tasks; i++) {
 
MPI_Send(&num_elements_per_proc[i], 1, MPI_INT, i, 0, MPI_COMM_WORLD);
 
}
 
 
boundary = step;
 
bucket_no = 1;
 
for(; boundary <= max; boundary += step, ++bucket_no) {
 
i = 0;
 
for(; i < num_elements; i++) {
 
if(rand_nums[i] > boundary - step && rand_nums[i] <= boundary) {
 
MPI_Send(&rand_nums[i], 1, MPI_INT, bucket_no, 1, MPI_COMM_WORLD);
 
}
 
}
 
}
 
 
total_distribution_time += MPI_Wtime();
 
 
total_sort_time -= MPI_Wtime();
 
 
i = 1;
 
int mergeidx = 0;
 
for(; i < num_tasks; i++) {
 
int* inmsg = (int *)malloc(sizeof(int) * num_elements_per_proc[i]);
 
 
MPI_Recv(inmsg, num_elements_per_proc[i], MPI_INT, i, 2, MPI_COMM_WORLD, &stat);
 
int j = 0;
 
for(; j<num_elements_per_proc[i]; j++) {
 
sorted_numbers[mergeidx++] = inmsg[j];
 
}
 
}
 
 
total_sort_time += MPI_Wtime();
 
 
printf("Distribution time = %lf\n", total_distribution_time);
 
printf("Sort time = %lf\n", total_sort_time);
 
 
printf("Sorted numbers :\n");
 
i = 0;
 
for (;i<num_elements;i++){
 
printf("%d ", sorted_numbers[i]);
 
}
 
} else {
 
int num_elements_received, temp;
 
MPI_Recv(&num_elements_received, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &stat);
 
 
int *bucket = (int *)malloc(sizeof(int) * num_elements_received);
 
int i = 0;
 
 
for(; i < num_elements_received; i++) {
 
MPI_Recv(&temp, 1, MPI_INT, 0, 1, MPI_COMM_WORLD, &stat);
 
bucket[i] = temp;
 
}
 
 
insertion_sort(bucket, num_elements_received);
 
MPI_Send(bucket, num_elements_received, MPI_INT, 0, 2, MPI_COMM_WORLD);
 
}
 
 
MPI_Finalize();
 
return 0;
 
}