Write a program to randomly generate the following sets of data: 1. 10 numbers 2
ID: 3816058 • Letter: W
Question
Write a program 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:
a) Insertion Sort
b) Heap Sort
Print out the time each algorithm takes to sort the above numbers. Your program needs to produce the following output:
Insertion Sort:
1. 10 numbers:
Data Generated:
Sorted Data:
Time
2. 1,000 numbers, time:
3. 100,000 numbers, time:
4. 1,000,000 numbers, time:
5. 10,000,000 numbers, time:
Heap Sort:
1. 10 numbers:
Data Generated:
Sorted Data:
Time:
2. 1,000 numbers, time:
3. 100,000 numbers, time:
4. 1,000,000 numbers, time:
5. 10,000,000 numbers, time:
Explanation / Answer
here is your program in Java. Please note that output may take considerable amount of time to come up because of high number of elements. Because of shorter time available, I have just printerd out the results for first three types of arrays i.e. for 10,1000,100000 numbers of arrays.
import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.TimeUnit;
public class MainDriver {
private static int N;
public static void main(String[] args) {
int[] arr1 = new int[10];
int[] arr2 = new int[1000];
int[] arr3 = new int[100000];
int[] arr4 = new int[1000000];
int[] arr5 = new int[10000000];
int[] arr6 = new int[10]; // for heap sort
int[] arr7 = new int[1000];
int[] arr8 = new int[100000];
int[] arr9 = new int[1000000];
int[] arr10 = new int[10000000];
// Generating random numbers form 1 to 10 for arr1
for (int i = 0; i < 10; i++) {
Random rand = new Random();
// Here 10 is max and 1 is min
arr1[i] = rand.nextInt(10) + 1;
}
// Generating random numbers form 1 to 1000 for arr2
for (int i = 0; i < 1000; i++) {
Random rand = new Random();
// Here 1000 is max and 1 is min
arr2[i] = rand.nextInt(1000) + 1;
}
// Generating random numbers form 1 to 100000 for arr3
for (int i = 0; i < 100000; i++) {
Random rand = new Random();
// Here 100000 is max and 1 is min
arr3[i] = rand.nextInt(100000) + 1;
}
// Generating random numbers form 1 to 1000000 for arr4
for (int i = 0; i < 1000000; i++) {
Random rand = new Random();
// Here 1000000 is max and 1 is min
arr4[i] = rand.nextInt(1000000) + 1;
}
// Generating random numbers form 1 to 10000000 for arr5
for (int i = 0; i < 10000000; i++) {
Random rand = new Random();
// Here 10000000 is max and 1 is min
arr5[i] = rand.nextInt(10000000) + 1;
}
arr6 = Arrays.copyOf(arr1, arr1.length);// copying data for heap
arr7 = Arrays.copyOf(arr2, arr2.length);
arr8 = Arrays.copyOf(arr3, arr3.length);
arr9 = Arrays.copyOf(arr4, arr4.length);
arr10 = Arrays.copyOf(arr5, arr5.length);
System.out.println("Insertion Sort");
System.out.println("1. 10 numbers:");
System.out.print("Data Generated:");
for (int i = 0; i < 10; i++) {
System.out.print(arr1[i] + " ");
}
System.out.println();
long startTime = System.nanoTime();
inSort(arr1);
long endTime = System.nanoTime();
long duration = (endTime - startTime);
System.out.print("Sorted Data:");
for (int i = 0; i < 10; i++) {
System.out.print(arr1[i] + " ");
}
System.out.println();
System.out.println("Time: " + duration + "ns");
startTime = System.nanoTime();
inSort(arr2);
endTime = System.nanoTime();
duration = (endTime - startTime);
System.out.println("2. 1,000 numbers, time:" + duration + "ns");
startTime = System.nanoTime();
inSort(arr3);
endTime = System.nanoTime();
duration = (endTime - startTime);
System.out.println("3. 100,000 numbers, time:" + duration + "ns");
startTime = System.nanoTime();
inSort(arr4);
endTime = System.nanoTime();
duration = (endTime - startTime);
System.out.println("4. 1000,000 numbers, time:" + duration + "ns");
startTime = System.nanoTime();
inSort(arr5);
endTime = System.nanoTime();
duration = (endTime - startTime);
System.out.println("5. 10,000,000 numbers, time:" + duration + "ns");
// for Heap Sort
System.out.println("Heap Sort");
System.out.println("1. 10 numbers:");
System.out.print("Data Generated:");
for (int i = 0; i < 10; i++) {
System.out.print(arr6[i] + " ");
}
System.out.println();
startTime = System.nanoTime();
hpSort(arr6);
endTime = System.nanoTime();
duration = (endTime - startTime);
System.out.print("Sorted Data:");
for (int i = 0; i < 10; i++) {
System.out.print(arr6[i] + " ");
}
System.out.println();
System.out.println("Time: " + duration + "ns");
startTime = System.nanoTime();
hpSort(arr7);
endTime = System.nanoTime();
duration = (endTime - startTime);
System.out.println("2. 1,000 numbers, time:" + duration + "ns");
startTime = System.nanoTime();
hpSort(arr8);
endTime = System.nanoTime();
duration = (endTime - startTime);
System.out.println("3. 100,000 numbers, time:" + duration + "ns");
startTime = System.nanoTime();
hpSort(arr9);
endTime = System.nanoTime();
duration = (endTime - startTime);
System.out.println("4. 1000,000 numbers, time:" + duration + "ns");
startTime = System.nanoTime();
hpSort(arr10);
endTime = System.nanoTime();
duration = (endTime - startTime);
System.out.println("5. 10,000,000 numbers, time:" + duration + "ns");
}
public static void inSort(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j - 1;
while ((i > -1) && (array[i] > key)) {
array[i + 1] = array[i];
i--;
}
array[i + 1] = key;
}
}
public static void hpSort(int arr[]) {
heapify(arr);
for (int i = N; i > 0; i--) {
swap(arr, 0, i);
N = N - 1;
maxheap(arr, 0);
}
}
/* Function to build a heap */
public static void heapify(int arr[]) {
N = arr.length - 1;
for (int i = N / 2; i >= 0; i--)
maxheap(arr, i);
}
/* Function to swap largest element in heap */
public static void maxheap(int arr[], int i) {
int left = 2 * i;
int right = 2 * i + 1;
int max = i;
if (left <= N && arr[left] > arr[i])
max = left;
if (right <= N && arr[right] > arr[max])
max = right;
if (max != i) {
swap(arr, i, max);
maxheap(arr, max);
}
}
/* Function to swap two numbers in an array */
public static void swap(int arr[], int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
Output: - (for 1 to 3)
Insertion Sort
1. 10 numbers:
Data Generated:10 6 3 7 10 9 8 9 2 4
Sorted Data:2 3 4 6 7 8 9 9 10 10
Time: 12129ns
2. 1,000 numbers, time:7429717ns
3. 100,000 numbers, time:5132460391ns
Heap Sort
1. 10 numbers:
Data Generated:10 6 3 7 10 9 8 9 2 4
Sorted Data:2 3 4 6 7 8 9 9 10 10
Time: 58314ns
2. 1,000 numbers, time:1042195ns
3. 100,000 numbers, time:24394067ns
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.