Implement MERGE-SORT() algorithm that reads from a file named “inputHW02.txt” a

Question

Implement MERGE-SORT() algorithm that reads from a file named “inputHW02.txt” a list of double numbers (max = 3,000,000), sorts those numbers and indicates time consumption. This programming question will address the advantage of using iteration loops over recursive calls as well as using INSERTION-SORT() as a procedure in MERGE-SORT().

Your program must perform the following actions:

1. Opens the given file name and reads all double numbers. For simplicity, we assume this file only contains numbers and nothing else.

2. Implements the function INSERTION-SORT() that only sort an array of max size 25 numbers. The idea is that INSERTION-SORT() will be used as a sub-procedure to sort any sub-array when its size is small enough.

3. Four versions of MERGE-SORT() namely a. MERGE-SORT-A(): Using recursive calls and NO INSERTION-SORT() as a sub-procedure b. MERGE-SORT-B(): Using ITERATIVE loops (i.e, NO recursion) and NO INSERTION-SORT() as a subprocedure. c. MERGE-SORT-C(): Using recursive calls and INSERTION-SORT() as a sub-procedure. d. MERGE-SORT-D(): Using ITERATIVE loops (i.e, NO recursion) and INSERTION-SORT() as a subprocedure.

4. For testing purpose, write another procedure to randomly generate N numbers and write them to a given file name filename where N and filename are input parameters.

Report your MERGE-SORT() time consumption on the following input sizes: N = 1M, 1.5M, 2M, 2.5M and 3M numbers. That is, for each input size N, calls (4) to generate N numbers and write them to the given file name. Then reads from that file and performs MERGE-SORT-A(), MERGE-SORT-B(), MERGE-SORT-C(), MERGE-SORTD() and report each of their time consumptions in a graph. Overall 20 graphs are expected.

Explanation / Answer

import java.util.Scanner;

/* Class MergeSort */
public class MergeSort
{
/* Merge Sort function */
public static void sort(int[] a, int low, int high)
{
int N = high - low;
if (N <= 1)
return;
int mid = low + N/2;
// recursively sort
sort(a, low, mid);
sort(a, mid, high);
// merge two sorted subarrays
int[] temp = new int[N];
int i = low, j = mid;
for (int k = 0; k < N; k++)
{
if (i == mid)  
temp[k] = a[j++];
else if (j == high)
temp[k] = a[i++];
else if (a[j]<a[i])
temp[k] = a[j++];
else
temp[k] = a[i++];
}   
for (int k = 0; k < N; k++)
a[low + k] = temp[k];
}
/* Main method */
public static void main(String[] args)
{
Scanner scan = new Scanner( System.in );   
System.out.println("Merge Sort Test ");
int n, i;
/* Accept number of elements */
System.out.println("Enter number of integer elements");
n = scan.nextInt();
/* Create array of n elements */
int arr[] = new int[ n ];
/* Accept elements */
System.out.println(" Enter "+ n +" integer elements");
for (i = 0; i < n; i++)
arr[i] = scan.nextInt();
/* Call method sort */
sort(arr, 0, n);
/* Print sorted Array */
System.out.println(" Elements after sorting ");   
for (i = 0; i < n; i++)
System.out.print(arr[i]+" ");   
System.out.println();   
}   
}

insertion sort:
===============
public class InsertionSortExample {  
public static void insertionSort(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 main(String a[]){   
int[] arr1 = {9,14,3,2,43,11,58,22};   
System.out.println("Before Insertion Sort");   
for(int i:arr1){   
System.out.print(i+" ");   
}   
System.out.println();   
  
insertionSort(arr1);//sorting array using insertion sort   

System.out.println("After Insertion Sort");   
for(int i:arr1){   
System.out.print(i+" ");   
}   
}   
}   

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.