Homework SourseWrite a program any language to randomly generate the follow
Write a program (any language) 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) Merge Sort c) Quick Sort d) Heap Sort Print out the time each algorithm takes to sort the above numbers
Solution
import java.io.*;
public class randomNo{
public static void main(String[] args) throws NumberFormatException, IOException {
int n1,n2,ch;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int count = 0;
do
{
System.out.println(\"\ \");
System.out.println(\"Menu:\");
System.out.println(\"1.Insertion Sort\");
System.out.println(\"2.Heap Sort.\");
System.out.println(\"3.Quick SOrt\");
System.out.println(\"4.Merge SOrt\");
System.out.println(\"5.Exit\");
System.out.println(\"Enter your choice: \");
ch=Integer.parseInt(br.readLine());
switch(ch)
{
case 1:
System.out.println(\"Enter range to generate random numbers--Enter n1 & n2::\");
n1=Integer.parseInt(br.readLine());
n2=Integer.parseInt(br.readLine());
int[] arr=new int[n2];
for (int i = 0; i < 10 ; i++)
{
int Random = (n1) + (int)(Math.random()* ((n2-n1)+1));
arr[i]=Random;
System.out.println(Random);
count++;
}
insertionSort(arr,count);
break;
case 2:
System.out.println(\"Enter range to generate random numbers--Enter n1 & n2::\");
n1=Integer.parseInt(br.readLine());
n2=Integer.parseInt(br.readLine());
int[] arr1=new int[20];
for (int i = 0; i < 10 ; i++)
{
int Random = (n1) + (int)(Math.random()* ((n2-n1)+1));
arr1[i]=Random;
System.out.println(Random);
count++;
}
System.out.println(\"\ Before Sorting\");
for(int i=0; i<count; i++) {
System.out.print(\" \" + arr1[i]);
}
System.out.println(\"\ \ After Sorting\");
for(int i=count; i>1; i--) {
HeapSort(arr1, i - 1);
}
System.out.println(\"\ Ascending Order\");
for(int i=0; i<count; i++) {
System.out.print(\" \" + arr1[i]);
}
System.out.println(\"\ Descending Order\");
for(int i=count-1; i>=0; i--) {
System.out.print(\" \" + arr1[i]);
}
break;
case 3:
System.out.println(\"Enter range to generate random numbers--Enter n1 & n2::\");
n1=Integer.parseInt(br.readLine());
n2=Integer.parseInt(br.readLine());
int[] arr3=new int[20];
for (int i = 0; i < 10 ; i++)
{
int Random = (n1) + (int)(Math.random()* ((n2-n1)+1));
arr3[i]=Random;
System.out.println(Random);
count++;
}
QuickSort(arr3, 0, count-1);
System.out.println(\"\ \ After Sorting\");
System.out.println(\"\ Ascending Order\");
for(int i=0; i<count; i++) {
System.out.print(\" \" + arr3[i]);
}
System.out.println(\"\ Descending Order\");
for(int i=count-1; i>=0; i--) {
System.out.print(\" \" + arr3[i]);
}
break;
case 4:
System.out.println(\"Enter range to generate random numbers--Enter n1 & n2::\");
n1=Integer.parseInt(br.readLine());
n2=Integer.parseInt(br.readLine());
int[] arr2=new int[20];
for (int i = 0; i < 10 ; i++)
{
int Random = (n1) + (int)(Math.random()* ((n2-n1)+1));
arr2[i]=Random;
System.out.println(Random);
count++;
}
System.out.println(\"\ Before Sorting\");
for(int i=0; i<count; i++) {
System.out.print(\" \" + arr2[i]);
}
// Merge Sort Event..
MergeSort(arr2, 0, count-1);
System.out.println(\"\ \ After Sorting\");
System.out.println(\"\ Ascending Order\");
for(int i=0; i<count; i++) {
System.out.print(\" \" + arr2[i]);
}
System.out.println(\"\ Descending Order\");
for(int i=count-1; i>=0; i--) {
System.out.print(\" \" + arr2[i]);
}
break;
case 5:
System.out.println(\"Invalid\");
default:
break;
}
}while(ch!=5);
}
//Insertion Sort
public static void insertionSort(int arr[],int n){
System.out.println(\"\ Before Sorting :\");
for(int i=0; i<n; i++) {
System.out.print(arr[i] + \" \");
}
/* Insertion Sort Code Start */
for (int i = 1; i < n; i++) {
int j = i;
int B = arr[i];
while ((j > 0) && (arr[j-1] > B)) {
arr[j] = arr[j-1];
j--;
}
arr[j] = B;
}
/* Insertion Sort Code End */
System.out.println(\"\ \ After Sorting\");
System.out.println(\"\ Ascending Order :\");
for(int i=0; i<n; i++) {
System.out.print(\" \" + arr[i]);
}
System.out.println(\"\ Descending Order :\");
for(int i=n-1; i>=0; i--) {
System.out.print(\" \" + arr[i]);
}
}
//Heap Sort
private static void HeapSort(int[] arr, int bound) {
// TODO Auto-generated method stub
int left, right, middle, root, temp;
root = (bound-1) / 2;
for(int i=root; i>=0; i--) {
for(int j=root; j>=0; j--) {
left = (2*j) + 1;
right = (2*j) + 2;
if((left <= bound) && (right <= bound)) {
if(arr[right] >= arr[left])
middle = right;
else
middle = left;
}
else {
if(right > bound)
middle = left;
else
middle = right;
}
if(arr[j] < arr[middle]) {
temp = arr[j];
arr[j] = arr[middle];
arr[middle] = temp;
}
}
}
temp = arr[0];
arr[0] = arr[bound];
arr[bound] = temp;
}
//Merge Sort
private static void MergeSort(int[] num, int i, int j) {
int low = i;
int high = j;
if (low >= high) {
return;
}
int middle = (low + high) / 2;
MergeSort(num, low, middle);
MergeSort(num, middle + 1, high);
int end_low = middle;
int start_high = middle + 1;
while ((low <= end_low) && (start_high <= high)) {
if (num[low] < num[start_high]) {
low++;
}
else {
int Temp = num[start_high];
for (int k = start_high- 1; k >= low; k--) {
num[k+1] = num[k];
}
num[low] = Temp;
low ++;
end_low ++;
start_high ++;
}
}
}
private static void QuickSort(int[] num, int i, int j) {
int low = i;
int high = j;
if (low >= j) {
return;
}
int mid = num[(low + high) / 2];
while (low < high) {
while (low<high && num[low] < mid) {
low++;
}
while (low<high && num[high] > mid) {
high--;
}
if (low < high) {
int T = num[low];
num[low] = num[high];
num[high] = T;
}
}
}
}
