Parallel Sorting Algorithms- Bubble Sort and Merger Sort

Problem Statement:

Parallel Sorting Algorithms-
For Bubble Sort and Merger Sort, based on existing sequential algorithms, design and
implement parallel algorithm utilizing all resources available.

Source Code:

1. Bubble Sort

	#include <omp.h>
	#include <stdio.h>
	#include <stdlib.h>
	void swap();
	int main (int argc, char *argv[]) {
	int SIZE =1<<8;
	int A[SIZE];
	for(int i=0;i<SIZE;i++)
	{
	A[i]=rand()%SIZE;
	}
	//int A[5] = {6,9,1,3,7};
	int N = SIZE;
	int i=0, j=0;
	int first;
	double start,end;
	start=omp_get_wtime();
	for( i = 0; i < N-1; i++ )
	{
	first = i % 2;
	#pragma omp parallel for default(none),shared(A,first,N)
	for( j = first; j < N-1; j += 1 )
	{
	if( A[ j ] > A[ j+1 ] )
	{
	swap( &A[ j ], &A[ j+1 ] );
	}
	}
	}
	end=omp_get_wtime();
	for(i=0;i<N;i++)
	{
	printf(" %d",A[i]);
	}
	printf("\n-------------------------\n Time Parallel= %f",(end-start));
	}
	void swap(int *num1, int *num2)
	{
	int temp = *num1;
	*num1 = *num2;
	*num2 = temp;
	}

view raw bubbleSort.c hosted with ❤ by GitHub
Output:-

2. Merge Sort

	#include <stdio.h>
	#include <string.h>
	#include <stdlib.h>
	#include "omp.h"
	#define MAX_SIZE 10
	//Function for creating an input array||Update accoorind to your need
	void generate_list(int * x, int n) {
	int i,j,t;
	for (i = 0; i < n; i++)
	x[i] = i;
	for (i = 0; i < n; i++) {
	j = rand() % n;
	t = x[i];
	x[i] = x[j];
	x[j] = t;
	}
	}
	void print_list(int * x, int n) {
	int i;
	for (i = 0; i < n; i++) {
	printf("%d ",x[i]);
	}
	}
	//Merging 2 sorted subarrays into one tmp array
	void merge(int * X, int n, int * tmp) {
	int i = 0;
	int j = n/2;
	int ti = 0;
	//i will iterate till first half anf J will iterate for 2nd half of array
	while (i<n/2 && j<n) {
	if (X[i] < X[j]) {
	tmp[ti] = X[i];
	ti++; i++;
	} else {
	tmp[ti] = X[j];
	ti++;
	j++;
	}
	}
	while (i<n/2) { /* finish up lower half */
	tmp[ti] = X[i];
	ti++;
	i++;
	}
	while (j<n) { /* finish up upper half */
	tmp[ti] = X[j];
	ti++;
	j++;
	}
	//Copy sorted array tmp back to X (Original array)
	memcpy(X, tmp, n*sizeof(int));
	} // end of merge()
	void mergesort(int * X, int n, int * tmp)
	{
	if (n < 2) return;
	#pragma omp task firstprivate (X, n, tmp)
	mergesort(X, n/2, tmp);
	#pragma omp task firstprivate (X, n, tmp)
	mergesort(X+(n/2), n-(n/2), tmp);
	//Wait for both paralel tasks to complete execution
	#pragma omp taskwait
	/* merge sorted halves into sorted list */
	merge(X, n, tmp);
	}
	int main()
	{
	int n = 10;
	double start, stop;
	int data[MAX_SIZE], tmp[MAX_SIZE];
	generate_list(data, n);
	printf("List Before Sorting...\n");
	print_list(data, n);
	start = omp_get_wtime();
	#pragma omp parallel
	{
	#pragma omp single
	mergesort(data, n, tmp);
	}
	stop = omp_get_wtime();
	printf("\nList After Sorting...\n");
	print_list(data, n);
	printf("\nTime: %g\n",stop-start);
	}
	/*output
	root@kali:~/BE 1/HPC/OpenMP# gcc -fopenmp merge.c -o merge
	root@kali:~/BE 1/HPC/OpenMP# ./merge
	List Before Sorting...
	3 8 2 4 5 0 1 7 9 6
	List After Sorting...
	0 1 2 3 4 5 6 7 8 9
	root@kali:~/BE 1/HPC/OpenMP#
	*/

view raw mergeSort.c hosted with ❤ by GitHub
Output:-