SHARE
TWEET

Untitled

a guest Dec 9th, 2019 76 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top