Advertisement
Guest User

Untitled

a guest
Jul 27th, 2017
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.73 KB | None | 0 0
  1. /**
  2.  * @(#)Lab3.java
  3.  *
  4.  * Lab3 application
  5.  *
  6.  * @author
  7.  * @version 1.00 2011/2/20
  8.  */
  9. import java.util.*;
  10.  
  11.  
  12. public class Lab3 {
  13.  
  14.     public static void main(String[] args) {
  15.     System.out.println("It took : " + SortedArray500() + " NanoSeconds to find the element in array size 500");
  16.     System.out.println("It took : " + SortedArray1000() + " NanoSeconds to find the element in array size 1000");
  17.     System.out.println("It took : " + SortedArray2000() + " NanoSeconds to find the element in array size 2000");
  18.     System.out.println("It took : " + UnSorted500() + " NanoSeconds to find the element in UnSorted array size 500");
  19.     System.out.println("It took : " + UnSorted1000() + " NanoSeconds to find the element in UnSorted array size 1000");
  20.     System.out.println("It took : " + UnSorted2000() + " NanoSeconds to find the element in UnSorted array size 2000");
  21.     }
  22.  
  23.  
  24.  
  25.     // SORTED METHODS BINARY SEARCH!!!!!
  26.     public static long SortedArray500()
  27.     {
  28.        
  29.         int [] SArray500 = new int [500]; // Create Array of 500
  30.         int low = 0;
  31.         int high = SArray500.length-1;
  32.         int mid = (low+high)/2;
  33.         boolean found = false;
  34.        
  35.         Random generator = new Random(); // Create Random number generator
  36.         int r = generator.nextInt(500); // Random generator to create numbers from 0-499
  37.  
  38.         for (int i = 0; i < SArray500.length; i++)
  39.             SArray500[i] = i;
  40.  
  41.         int i = generator.nextInt(500); // Random generator to create numbers from 0-499
  42.         long beforeMethod = System.nanoTime();
  43.         while (!found)  // While loop for binary search
  44.         {
  45.             if (mid == i)
  46.             {
  47.                 found = true;
  48.             }
  49.             if (i < mid)
  50.             {
  51.                 high = mid;
  52.                 mid = (low + mid)/2;
  53.             }  
  54.             if (i > mid)
  55.             {
  56.                 low = mid;
  57.                 mid = (mid+high)/2;
  58.             }          
  59.         }
  60.         long afterMethod = System.nanoTime();
  61.         return (afterMethod-beforeMethod);
  62.     }
  63.     public static long SortedArray1000()
  64.     {
  65.         int [] SArray1000 = new int [1000]; // Create Array of 1000
  66.         boolean found = false;
  67.         int low = 0;
  68.         int high = SArray1000.length-1;
  69.         int mid = (low+high)/2;
  70.         Random generator = new Random(); // Create Random number generator
  71.         int r = generator.nextInt(1000);    // Random generator to create numbers from 0-999
  72.  
  73.         for (int i = 0; i < SArray1000.length; i++)
  74.         {
  75.             SArray1000[i] = i;
  76.         }
  77.  
  78.         int i = generator.nextInt(1000);    // Random generator to create numbers from 0-999
  79.         long beforeMethod = System.nanoTime();
  80.         while (!found)  // While loop for binary search
  81.         {
  82.             if (mid == i)
  83.             {
  84.                 found = true;
  85.             }
  86.             if (i < mid)
  87.             {
  88.                 high = mid;
  89.                 mid = (low + mid)/2;
  90.             }  
  91.             if (i > mid)
  92.             {
  93.                 low = mid;
  94.                 mid = (mid+high)/2;
  95.             }          
  96.         }
  97.         long afterMethod = System.nanoTime();
  98.         return (afterMethod-beforeMethod);
  99.     }
  100.     public static long SortedArray2000()
  101.     {
  102.         int [] SArray2000 = new int [2000]; // Create Array of 2000
  103.         boolean found = false;
  104.         int low = 0;
  105.         int high = SArray2000.length-1;
  106.         int mid = (low+high)/2;
  107.         Random generator = new Random(); // Create Random number generator
  108.         int r = generator.nextInt(2000);    // Random generator to create numbers from 0-1999
  109.  
  110.         for (int i = 0; i < SArray2000.length; i++)
  111.         {
  112.             SArray2000[i] = i;
  113.         }
  114.  
  115.         int i = generator.nextInt(200); // Random generator to create numbers from 0-1999
  116.         long beforeMethod = System.nanoTime();
  117.         while (!found)  // While loop for binary search
  118.         {
  119.             if (mid == i)
  120.             {
  121.                 found = true;
  122.             }
  123.             if (i < mid)
  124.             {
  125.                 high = mid;
  126.                 mid = (low + mid)/2;
  127.             }  
  128.             if (i > mid)
  129.             {
  130.                 low = mid;
  131.                 mid = (mid+high)/2;
  132.             }          
  133.         }
  134.         long afterMethod = System.nanoTime();
  135.         return (afterMethod-beforeMethod);
  136.     }
  137.     // UNSORTED METHODS
  138.  
  139.     public static long UnSorted500()
  140.     {
  141.         int[] sortedArray500 = new int [500]; // Create Array of 500
  142.         int[] unsortedArray500 = new int[500];
  143.         Random generator = new Random(); // Create Random number generator
  144.         int r = generator.nextInt(500); // Random generator to create numbers from 0-499
  145.         for (int i = 0; i < sortedArray500.length; i++)
  146.             sortedArray500[i] = i;
  147.  
  148.         int k = 0;
  149.             while(k < unsortedArray500.length)
  150.             {
  151.                     r = generator.nextInt(500);
  152.                     if(sortedArray500[r] != -1)
  153.                     {
  154.                         unsortedArray500[k] = sortedArray500[r];
  155.                         sortedArray500[r] = -1;
  156.                         k++;
  157.                     }
  158.             }
  159.         r = generator.nextInt(500);
  160.         long beforeMethod = System.nanoTime();
  161.         int i = 0;
  162.         while (unsortedArray500[i] != r)    // Search for random number if not found go on to next element.
  163.         {
  164.             i++;
  165.         }
  166.         long afterMethod = System.nanoTime();
  167.         return (afterMethod-beforeMethod);
  168.     }
  169.     public static long UnSorted1000()
  170.     {
  171.         int[] sortedArray1000 = new int [1000]; // Create Array of 1000
  172.         int[] unsortedArray1000 = new int[1000];
  173.         Random generator = new Random(); // Create Random number generator
  174.         int r = generator.nextInt(1000);    // Random generator to create numbers from 0-999
  175.         for (int i = 0; i < sortedArray1000.length; i++)
  176.             sortedArray1000[i] = i;
  177.  
  178.         int k = 0;
  179.             while(k < unsortedArray1000.length)
  180.             {
  181.                     r = generator.nextInt(1000);
  182.                     if(sortedArray1000[r] != -1)
  183.                     {
  184.                         unsortedArray1000[k] = sortedArray1000[r];
  185.                         sortedArray1000[r] = -1;
  186.                         k++;
  187.                     }
  188.             }
  189.         r = generator.nextInt(1000);
  190.         long beforeMethod = System.nanoTime();
  191.         int i = 0;
  192.         while (unsortedArray1000[i] != r)   // Search for random number if not found go on to next element.
  193.         {
  194.             i++;
  195.         }
  196.         long afterMethod = System.nanoTime();
  197.         return (afterMethod-beforeMethod); 
  198.     }
  199.         // UNSORTED 2000
  200.         public static long UnSorted2000()
  201.     {
  202.         int[] sortedArray2000 = new int [2000]; // Create Array of 2000
  203.         int[] unsortedArray2000 = new int[2000];
  204.         Random generator = new Random(); // Create Random number generator
  205.         int r = generator.nextInt(2000);    // Random generator to create numbers from 0-1999
  206.         for (int i = 0; i < sortedArray2000.length; i++)
  207.             sortedArray2000[i] = i;
  208.  
  209.         int k = 0;
  210.             while(k < unsortedArray2000.length)
  211.             {
  212.                     r = generator.nextInt(2000);
  213.                     if(sortedArray2000[r] != -1)
  214.                     {
  215.                         unsortedArray2000[k] = sortedArray2000[r];
  216.                         sortedArray2000[r] = -1;
  217.                         k++;
  218.                     }
  219.             }
  220.         r = generator.nextInt(2000);
  221.         long beforeMethod = System.nanoTime();
  222.         int i = 0;
  223.         while (unsortedArray2000[i] != r)   // Search for random number if not found go on to next element.
  224.         {
  225.             i++;
  226.         }
  227.         long afterMethod = System.nanoTime();
  228.         return (afterMethod-beforeMethod); 
  229.     }
  230. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement