Write a java program to randomly generate the following sets of data.pdf

Write a java program to randomly generate the following sets of data.pdf

• 1.
  Write a javaprogram to randomly generate the following sets of data: 1.) 10 numbers 2.) 1,000 numbers 3.) 100,000 numbers 4.) 1,000,000 numbers 5.) 10,000,000 numbers Your program must sort the above sets of numbers using the following algorithms: 1.) Insertion Sort 2.) Merge Sort 3.) Quick Sort 4.) Heap Sort Print out the time each algorithm takes to sort the above numbers Solution import java.util.Random; public class Sort { private int[] array; private int size ; public Sort(int n){ array = new int[n]; size = n; Random rand = new Random(); for (int i = 0 ; i < n ; i++ ) { array[i] = rand.nextInt(100000) ; } } public void print(){ for (int i = 0; i < size ; i++ ) { System.out.print(array[i] + " "); } System.out.println("");
• 2.
  } void insertion_sort() { for (inti=1; i=0 && array[j] > key) { array[j+1] = array[j]; j = j-1; } array[j+1] = key; } } void merge(int arr[], int l, int m, int r) { // Find sizes of two subarrays to be merged int n1 = m - l + 1; int n2 = r - m; /* Create temp arrays */ int L[] = new int [n1]; int R[] = new int [n2]; /*Copy data to temp arrays*/ for (int i=0; i Array to be sorted, low --> Starting index, high --> Ending index */ void quick_sort(int low, int high) { if (low < high) { /* pi is partitioning index, arr[pi] is now at right place */ int pi = partition(array, low, high); // Recursively sort elements before // partition and after partition
• 3.
  quick_sort(low, pi-1); quick_sort(pi+1, high); } } publicvoid heap_sort() { int n = array.length; // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) heapify(array, n, i); // One by one extract an element from heap for (int i=n-1; i>=0; i--) { // Move current root to end int temp = array[0]; array[0] = array[i]; array[i] = temp; // call max heapify on the reduced heap heapify(array, i, 0); } } // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap void heapify(int arr[], int n, int i) { int largest = i; // Initialize largest as root int l = 2*i + 1; // left = 2*i + 1 int r = 2*i + 2; // right = 2*i + 2 // If left child is larger than root if (l < n && arr[l] > arr[largest])
• 4.
  largest = l; //If right child is larger than largest so far if (r < n && arr[r] > arr[largest]) largest = r; // If largest is not root if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } public static void main(String[] args) { Sort sort1 = new Sort(10); long start = System.currentTimeMillis(); sort1.insertion_sort(); long time = System.currentTimeMillis() - start; //sort1.print(); System.out.println("insertion_sort for 10 numbers take " + time + " ms "); sort1 = new Sort(10); start = System.currentTimeMillis(); sort1.merge_sort(0,9); time = System.currentTimeMillis() - start; //sort1.print(); System.out.println("merge_sort for 10 numbers take " + time + " ms "); sort1 = new Sort(10); start = System.currentTimeMillis(); sort1.quick_sort(0,9); time = System.currentTimeMillis() - start; //sort1.print();
• 5.
  System.out.println("quick_sort for 10numbers take " + time + " ms "); sort1 = new Sort(10); start = System.currentTimeMillis(); sort1.heap_sort(); time = System.currentTimeMillis() - start; //sort1.print(); System.out.println("heap_sort for 10 numbers take " + time + " ms "); //////////////////////////////////////////////////////////////////////// System.out.println("");System.out.println(""); sort1 = new Sort(1000); start = System.currentTimeMillis(); sort1.insertion_sort(); time = System.currentTimeMillis() - start; System.out.println("insertion_sort for 1000 numbers take " + time + " ms "); sort1 = new Sort(1000); start = System.currentTimeMillis(); sort1.merge_sort(0,9); time = System.currentTimeMillis() - start; System.out.println("merge_sort for 1000 numbers take " + time + " ms "); sort1 = new Sort(1000); start = System.currentTimeMillis(); sort1.quick_sort(0,9); time = System.currentTimeMillis() - start; System.out.println("quick_sort for 1000 numbers take " + time + " ms "); sort1 = new Sort(1000); start = System.currentTimeMillis(); sort1.heap_sort(); time = System.currentTimeMillis() - start; System.out.println("heap_sort for 1000 numbers take " + time + " ms ");
• 6.
  //////////////////////////////////////////////////////////////////////// System.out.println("");System.out.println(""); sort1 = newSort(100000); start = System.currentTimeMillis(); sort1.insertion_sort(); time = System.currentTimeMillis() - start; System.out.println("insertion_sort for 100000 numbers take " + time + " ms "); sort1 = new Sort(100000); start = System.currentTimeMillis(); sort1.merge_sort(0,9); time = System.currentTimeMillis() - start; System.out.println("merge_sort for 100000 numbers take " + time + " ms "); sort1 = new Sort(100000); start = System.currentTimeMillis(); sort1.quick_sort(0,9); time = System.currentTimeMillis() - start; System.out.println("quick_sort for 100000 numbers take " + time + " ms "); sort1 = new Sort(100000); start = System.currentTimeMillis(); sort1.heap_sort(); time = System.currentTimeMillis() - start; System.out.println("heap sort for 100000 numbers take " + time + " ms "); //////////////////////////////////////////////////////////////////////// System.out.println("");System.out.println(""); sort1 = new Sort(1000000); start = System.currentTimeMillis(); sort1.insertion_sort(); time = System.currentTimeMillis() - start;
• 7.
  System.out.println("insertion_sort for 1000000numbers take " + time + " ms "); sort1 = new Sort(1000000); start = System.currentTimeMillis(); sort1.merge_sort(0,9); time = System.currentTimeMillis() - start; System.out.println("merge_sort for 1000000 numbers take " + time + " ms "); sort1 = new Sort(1000000); start = System.currentTimeMillis(); sort1.quick_sort(0,9); time = System.currentTimeMillis() - start; System.out.println("quick_sort for 1000000 numbers take " + time + " ms "); sort1 = new Sort(1000000); start = System.currentTimeMillis(); sort1.heap_sort(); time = System.currentTimeMillis() - start; System.out.println("heap_sort for 1000000 numbers take " + time + " ms "); //////////////////////////////////////////////////////////////////////// System.out.println("");System.out.println(""); sort1 = new Sort(10000000); start = System.currentTimeMillis(); sort1.insertion_sort(); time = System.currentTimeMillis() - start; System.out.println("insertion_sort for 10000000 numbers take " + time + " ms "); sort1 = new Sort(10000000); start = System.currentTimeMillis(); sort1.merge_sort(0,9); time = System.currentTimeMillis() - start; System.out.println("merge_sort for 10000000 numbers take " + time + " ms "); sort1 = new Sort(10000000);
• 8.
  start = System.currentTimeMillis(); sort1.quick_sort(0,9); time= System.currentTimeMillis() - start; System.out.println("quick_sort for 10000000 numbers take " + time + " ms "); sort1 = new Sort(10000000); start = System.currentTimeMillis(); sort1.heap_sort(); time = System.currentTimeMillis() - start; } } Sample Output insertion_sort for 10 numbers take 0 ms merge_sort for 10 numbers take 0 ms quick_sort for 10 numbers take 0 ms heap_sort for 10 numbers take 0 ms insertion_sort for 1000 numbers take 5 ms merge_sort for 1000 numbers take 0 ms quick_sort for 1000 numbers take 0 ms heap_sort for 1000 numbers take 6 ms insertion_sort for 100000 numbers take 1239 ms merge_sort for 100000 numbers take 0 ms quick_sort for 100000 numbers take 0 ms heap sort for 100000 numbers take 21 ms insertion_sort for 1000000 numbers take 217971 ms merge_sort for 1000000 numbers take 0 ms quick_sort for 1000000 numbers take 0 ms heap_sort for 1000000 numbers take 261 ms