Guest User

Untitled

a guest
Dec 9th, 2019
89
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* Name: Chris Torrella
  2. * COSC 311 FA19
  3. * Final Project
  4. * URL:
  5. */
  6.  
  7.  
  8. package mergeSort;
  9. //import java.util.Arrays;
  10. import java.util.Random;
  11.  
  12.  
  13. public class MS_Internal {
  14. public static void main(String args[]) {
  15.  
  16. System.out.println("Size of data; Time taken to sort (ms)");
  17. Random r = new Random(97);
  18.  
  19. int[][] MSEA = new int[100][2];
  20.  
  21. for(int i = 100000; i <= 10000000; i+= 100000) {
  22. //go through datasets size 1 to 50
  23.  
  24. //create array, fill with data
  25. int[] sortMe = new int[i];
  26. for (int j = 0; j < sortMe.length; j++) {
  27. sortMe[j] = r.nextInt(300);
  28. }
  29.  
  30. //get time start
  31. long timeStart = System.currentTimeMillis();
  32. mergeSort(sortMe, sortMe.length);
  33. long timeEnd = System.currentTimeMillis();
  34. //calc time to sort
  35. long totalTime = timeEnd - timeStart;
  36.  
  37. System.out.println(i + "; " + totalTime + "ms");
  38. MSEA[(i / 100000) - 1][0] = i;
  39. MSEA[(i / 100000) - 1][1] = (int)totalTime;
  40.  
  41. }
  42.  
  43. float MSE = 0;
  44.  
  45. for (int i = 0; i < 100; i++){
  46. MSE += Math.pow((MSEA[i][0] - MSEA[i][1]), 2);
  47. }
  48.  
  49. MSE *= (1/100);
  50.  
  51. System.out.println("MSE is " + MSE);
  52.  
  53.  
  54. }
  55.  
  56. public static void merge( int[] a, int[] l, int[] r, int leftSize, int rightSize) {
  57.  
  58. //setup loop variables
  59. int i = 0, j = 0, k = 0;
  60.  
  61. //sort while the bottom or top haven't been exhausted
  62. while (i < leftSize && j < rightSize) {
  63. //if left el @i is less than right el @j
  64. if (l[i] <= r[j]) {
  65. //update element for a
  66. a[k] = l[i];
  67. //increment pointers
  68. k++;
  69. i++;
  70. }
  71. else {
  72. //else use the other element
  73. a[k] = r[j];
  74. //increment pointers
  75. k++;
  76. j++;
  77. }
  78. }
  79.  
  80. //continue through all elements and add to a
  81. while (i < leftSize) {
  82. a[k] = l[i];
  83. k++;
  84. i++;
  85. }
  86.  
  87. //continue through all elements and add to a
  88. while (j < rightSize) {
  89. a[k] = r[j];
  90. k++;
  91. j++;
  92. }
  93.  
  94. }
  95.  
  96. public static void mergeSort(int[] a, int n) {
  97.  
  98.  
  99. //if there's one item, it's already sorted
  100. if (n < 2) {
  101. return;
  102. }
  103.  
  104. //calculate the middle index from n/2
  105. int middleIndex = n / 2;
  106.  
  107. //create new arrays for left and right, half and half
  108. int[] l = new int[middleIndex];
  109. int[] r = new int[n - middleIndex];
  110.  
  111. //copy first half of a into left array
  112. for (int i = 0; i < middleIndex; i++) {
  113. l[i] = a[i];
  114. }
  115. //copy second half of a into right array
  116. for (int i = middleIndex; i < n; i++) {
  117. r[i - middleIndex] = a[i];
  118. }
  119.  
  120. //sort the left half
  121. mergeSort(l, middleIndex);
  122. //sort the right half
  123. mergeSort(r, n - middleIndex);
  124.  
  125.  
  126. //merge the arrays
  127. merge(a, l, r, middleIndex, n - middleIndex);
  128.  
  129. }
  130. }
RAW Paste Data