fork download
copy 
  1. // C program to implement the Quick Sort
  2. // Algorithm using MPI
  3. #include <mpi.h>
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <time.h>
  7. #include <unistd.h>
  8. using namespace std;
  9.  
  10. // Function to swap two numbers
  11. void swap(int* arr, int i, int j)
  12. {
  13. 	int t = arr[i];
  14. 	arr[i] = arr[j];
  15. 	arr[j] = t;
  16. }
  17.  
  18. // Function that performs the Quick Sort
  19. // for an array arr[] starting from the
  20. // index start and ending at index end
  21. void quicksort(int* arr, int start, int end)
  22. {
  23. 	int pivot, index;
  24.  
  25. 	// Base Case
  26. 	if (end <= 1)
  27. 		return;
  28.  
  29. 	// Pick pivot and swap with first
  30. 	// element Pivot is middle element
  31. 	pivot = arr[start + end / 2];
  32. 	swap(arr, start, start + end / 2);
  33.  
  34. 	// Partitioning Steps
  35. 	index = start;
  36.  
  37. 	// Iterate over the range [start, end]
  38. 	for (int i = start + 1; i < start + end; i++) {
  39.  
  40. 		// Swap if the element is less
  41. 		// than the pivot element
  42. 		if (arr[i] < pivot) {
  43. 			index++;
  44. 			swap(arr, i, index);
  45. 		}
  46. 	}
  47.  
  48. 	// Swap the pivot into place
  49. 	swap(arr, start, index);
  50.  
  51. 	// Recursive Call for sorting
  52. 	// of quick sort function
  53. 	quicksort(arr, start, index - start);
  54. 	quicksort(arr, index + 1, start + end - index - 1);
  55. }
  56.  
  57. // Function that merges the two arrays
  58. int* merge(int* arr1, int n1, int* arr2, int n2)
  59. {
  60. 	int* result = (int*)malloc((n1 + n2) * sizeof(int));
  61. 	int i = 0;
  62. 	int j = 0;
  63. 	int k;
  64.  
  65. 	for (k = 0; k < n1 + n2; k++) {
  66. 		if (i >= n1) {
  67. 			result[k] = arr2[j];
  68. 			j++;
  69. 		}
  70. 		else if (j >= n2) {
  71. 			result[k] = arr1[i];
  72. 			i++;
  73. 		}
  74.  
  75. 		// Indices in bounds as i < n1
  76. 		// && j < n2
  77. 		else if (arr1[i] < arr2[j]) {
  78. 			result[k] = arr1[i];
  79. 			i++;
  80. 		}
  81.  
  82. 		// v2[j] <= v1[i]
  83. 		else {
  84. 			result[k] = arr2[j];
  85. 			j++;
  86. 		}
  87. 	}
  88. 	return result;
  89. }
  90.  
  91. // Driver Code
  92. int main(int argc, char* argv[])
  93. {
  94. 	int number_of_elements;
  95. 	int* data = NULL;
  96. 	int chunk_size, own_chunk_size;
  97. 	int* chunk;
  98. 	FILE* file = NULL;
  99. 	double time_taken;
  100. 	MPI_Status status;
  101.  
  102. 	if (argc != 3) {
  103. 		printf("Desired number of arguments are not their "
  104. 			"in argv....\n");
  105. 		printf("2 files required first one input and "
  106. 			"second one output....\n");
  107. 		exit(-1);
  108. 	}
  109.  
  110. 	int number_of_process, rank_of_process;
  111. 	int rc = MPI_Init(&argc, &argv);
  112.  
  113. 	if (rc != MPI_SUCCESS) {
  114. 		printf("Error in creating MPI "
  115. 			"program.\n "
  116. 			"Terminating......\n");
  117. 		MPI_Abort(MPI_COMM_WORLD, rc);
  118. 	}
  119.  
  120. 	MPI_Comm_size(MPI_COMM_WORLD, &number_of_process);
  121. 	MPI_Comm_rank(MPI_COMM_WORLD, &rank_of_process);
  122.  
  123. 	if (rank_of_process == 0) {
  124. 		// Opening the file
  125. 		file = fopen(argv[1], "r");
  126.  
  127. 		// Printing Error message if any
  128. 		if (file == NULL) {
  129. 			printf("Error in opening file\n");
  130. 			exit(-1);
  131. 		}
  132.  
  133. 		// Reading number of Elements in file ...
  134. 		// First Value in file is number of Elements
  135. 		printf(
  136. 			"Reading number of Elements From file ....\n");
  137. 		fscanf(file, "%d", &number_of_elements);
  138. 		printf("Number of Elements in the file is %d \n",
  139. 			number_of_elements);
  140.  
  141. 		// Computing chunk size
  142. 		chunk_size
  143. 			= (number_of_elements % number_of_process == 0)
  144. 				? (number_of_elements / number_of_process)
  145. 				: (number_of_elements / number_of_process
  146. 					- 1);
  147.  
  148. 		data = (int*)malloc(number_of_process * chunk_size
  149. 							* sizeof(int));
  150.  
  151. 		// Reading the rest elements in which
  152. 		// operation is being performed
  153. 		printf("Reading the array from the file.......\n");
  154. 		for (int i = 0; i < number_of_elements; i++) {
  155. 			fscanf(file, "%d", &data[i]);
  156. 		}
  157.  
  158. 		// Padding data with zero
  159. 		for (int i = number_of_elements;
  160. 			i < number_of_process * chunk_size; i++) {
  161. 			data[i] = 0;
  162. 		}
  163.  
  164. 		// Printing the array read from file
  165. 		printf("Elements in the array is : \n");
  166. 		for (int i = 0; i < number_of_elements; i++) {
  167. 			printf("%d ", data[i]);
  168. 		}
  169.  
  170. 		printf("\n");
  171.  
  172. 		fclose(file);
  173. 		file = NULL;
  174. 	}
  175.  
  176. 	// Blocks all process until reach this point
  177. 	MPI_Barrier(MPI_COMM_WORLD);
  178.  
  179. 	// Starts Timer
  180. 	time_taken -= MPI_Wtime();
  181.  
  182. 	// BroadCast the Size to all the
  183. 	// process from root process
  184. 	MPI_Bcast(&number_of_elements, 1, MPI_INT, 0,
  185. 			MPI_COMM_WORLD);
  186.  
  187. 	// Computing chunk size
  188. 	chunk_size
  189. 		= (number_of_elements % number_of_process == 0)
  190. 			? (number_of_elements / number_of_process)
  191. 			: number_of_elements
  192. 					/ (number_of_process - 1);
  193.  
  194. 	// Calculating total size of chunk
  195. 	// according to bits
  196. 	chunk = (int*)malloc(chunk_size * sizeof(int));
  197.  
  198. 	// Scatter the chuck size data to all process
  199. 	MPI_Scatter(data, chunk_size, MPI_INT, chunk,
  200. 				chunk_size, MPI_INT, 0, MPI_COMM_WORLD);
  201. 	free(data);
  202. 	data = NULL;
  203.  
  204. 	// Compute size of own chunk and
  205. 	// then sort them
  206. 	// using quick sort
  207.  
  208. 	own_chunk_size = (number_of_elements
  209. 					>= chunk_size * (rank_of_process + 1))
  210. 						? chunk_size
  211. 						: (number_of_elements
  212. 							- chunk_size * rank_of_process);
  213.  
  214. 	// Sorting array with quick sort for every
  215. 	// chunk as called by process
  216. 	quicksort(chunk, 0, own_chunk_size);
  217.  
  218. 	for (int step = 1; step < number_of_process;
  219. 		step = 2 * step) {
  220. 		if (rank_of_process % (2 * step) != 0) {
  221. 			MPI_Send(chunk, own_chunk_size, MPI_INT,
  222. 					rank_of_process - step, 0,
  223. 					MPI_COMM_WORLD);
  224. 			break;
  225. 		}
  226.  
  227. 		if (rank_of_process + step < number_of_process) {
  228. 			int received_chunk_size
  229. 				= (number_of_elements
  230. 				>= chunk_size
  231. 						* (rank_of_process + 2 * step))
  232. 					? (chunk_size * step)
  233. 					: (number_of_elements
  234. 						- chunk_size
  235. 							* (rank_of_process + step));
  236. 			int* chunk_received;
  237. 			chunk_received = (int*)malloc(
  238. 				received_chunk_size * sizeof(int));
  239. 			MPI_Recv(chunk_received, received_chunk_size,
  240. 					MPI_INT, rank_of_process + step, 0,
  241. 					MPI_COMM_WORLD, &status);
  242.  
  243. 			data = merge(chunk, own_chunk_size,
  244. 						chunk_received,
  245. 						received_chunk_size);
  246.  
  247. 			free(chunk);
  248. 			free(chunk_received);
  249. 			chunk = data;
  250. 			own_chunk_size
  251. 				= own_chunk_size + received_chunk_size;
  252. 		}
  253. 	}
  254.  
  255. 	// Stop the timer
  256. 	time_taken += MPI_Wtime();
  257.  
  258. 	// Opening the other file as taken form input
  259. 	// and writing it to the file and giving it
  260. 	// as the output
  261. 	if (rank_of_process == 0) {
  262. 		// Opening the file
  263. 		file = fopen(argv[2], "w");
  264.  
  265. 		if (file == NULL) {
  266. 			printf("Error in opening file... \n");
  267. 			exit(-1);
  268. 		}
  269.  
  270. 		// Printing total number of elements
  271. 		// in the file
  272. 		fprintf(
  273. 			file,
  274. 			"Total number of Elements in the array : %d\n",
  275. 			own_chunk_size);
  276.  
  277. 		// Printing the value of array in the file
  278. 		for (int i = 0; i < own_chunk_size; i++) {
  279. 			fprintf(file, "%d ", chunk[i]);
  280. 		}
  281.  
  282. 		// Closing the file
  283. 		fclose(file);
  284.  
  285. 		printf("\n\n\n\nResult printed in output.txt file "
  286. 			"and shown below: \n");
  287.  
  288. 		// For Printing in the terminal
  289. 		printf("Total number of Elements given as input : "
  290. 			"%d\n",
  291. 			number_of_elements);
  292. 		printf("Sorted array is: \n");
  293.  
  294. 		for (int i = 0; i < number_of_elements; i++) {
  295. 			printf("%d ", chunk[i]);
  296. 		}
  297.  
  298. 		printf(
  299. 			"\n\nQuicksort %d ints on %d procs: %f secs\n",
  300. 			number_of_elements, number_of_process,
  301. 			time_taken);
  302. 	}
  303.  
  304. 	MPI_Finalize();
  305. 	return 0;
  306. }
  307.  
Success #stdin #stdout #stderr 0.27s 40424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Error: unexpected '/' in "/"
Execution halted
https://ideone.com/Jozs3x
language:
R (R 3.5.2)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!