Guest User

Untitled

a guest
Mar 18th, 2018
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.54 KB | None | 0 0
  1. /* C program for Merge Sort */
  2. #include<stdlib.h>
  3. #include<stdio.h>
  4.  
  5. #define infinite 9999; //Used for sentinels
  6.  
  7. void MERGE(A, p, q, r);
  8. void printArray(Arr, size);
  9. void MERGE_SORT(A, p, r);
  10.  
  11. int main(void)
  12. {
  13. int A[] = { 12, 11, 13, 5, 6, 7, 2, 9 };
  14. int arr_size = sizeof(A) / sizeof(A[0]);
  15.  
  16. MERGE_SORT(A, 1, arr_size);
  17.  
  18. printf("nSorted array is n");
  19. printArray(A, arr_size);
  20.  
  21. return 0;
  22. }
  23.  
  24. void MERGE(int A[], int p, int q, int r)
  25. {
  26. int i = 0;
  27. int j =0;
  28. int n1 = q - p + 1; //Computing length of sub-array 1
  29. int n2 = r - q; //Computing length of sub-array 2
  30. int L[n1]; //Creating Left array
  31. int R[n2]; //Creating Right array
  32.  
  33. for (int i = 1; i < n1; i++) {
  34. L[i] = A[p + i - 1];
  35. }
  36. for (int j = 1; j < n2; j++) {
  37. L[j] = A[q + j];
  38. }
  39.  
  40. L[n1] = 99; //Placing Ssentinel at the end of array
  41. R[n2] = 99;
  42.  
  43. i = 1;
  44. j = 1;
  45.  
  46. /*Prior to the first iteration k = p, so the subarray is empty.
  47. Both L[i] and R[j] are the smallest elements of their arrays and have not
  48. been copied back to A*/
  49. for (int k = p; k < r; k++) {
  50. if (L[i] <= R[j]) {
  51. A[k] = L[i];
  52. i++;
  53. }
  54. else if (A[k] = L[i])
  55. j++;
  56. }
  57.  
  58. }
  59.  
  60. void MERGE_SORT(int A[], int p, int r)
  61. {
  62. //During first iteration p = 1 & r = 8
  63. if (p < r) {
  64. int q = (p + r) / 2;
  65. MERGE_SORT(A, p, q);
  66. MERGE_SORT(A, q + 1, r);
  67. MERGE(A, p, q, r);
  68. }
  69. }
  70.  
  71. int *L = malloc(n1 * sizeof(*L));
  72. if (L == NULL) {
  73. // handle error
  74. }
Add Comment
Please, Sign In to add comment