Question

Written in Java

Your job is to produce a program that sorts a list of numbers in ascending order. Your program will need to read-in, from a file, a list of integers – at which point you should allow the user an option to choose to sort the numbers in ascending order via one of the three Sorting algorithms that we have explored. Your program should use the concept of Polymorphism to provide this sorting feature. As output, you will display the sorted list back to the user.

A secondary task of this assignment is to provide runtime analysis of your program. As discussed in lecture, Big-O notation provides us a way to evaluate the performance of our code. You will provide in a separate text file the Big-O of the two sorting algorithms that we have implemented in this assignment.

This program will be written in Java.

Your program will be menu driven in which you will provide the following prompts to the user:

1. Load Integers (From File)

2. Exit Program

Once the user has loaded the list of integers the following options should be provided:

1. Insertion Sort

2. Bubble Sort

3. Exit Program

The text file containing integer data will be provided to you. The filename will be data.txt – this file can be found (and downloaded) on Canvas. The file will contain fifty integers (50) and they will be comma separated on a single line.

Example:

39,14,100,16,93,24,62,68,52,76,86,48,15,41,83,55,18,30,74,7,31,44,67,81

Your program must contain at-least four (4) classes.

o Driver

o Sort

o Insertion Sort

o Bubble Sort

o Quick Sort

You must use the concepts of Inheritance and Polymorphism in order to complete this assignment. o Your Sort class must be a pure virtual class.

o You should use proper OO approaches to implementing Inheritance.

• It is recommended you use stringstream to read-in and parse the data file.

• Your sample output must match that shown below – note that in order to “re-sort” the list you must also “re-load” the data file.

• You are required to use an Array to store the data read-in from the file.

• You are required to use the Heap to store your Objects in memory.

• You program should have no memory leaks – a memory leak will result in a deduction of points. o Make sure to run Valgrind against your submission to check for memory leaks and include this report with your submission.

• You are required to provide a brief (about one paragraph per algorithm) overview/analysis of the Big-O runtime of your program with respect to the two sorting algorithms we are implementing as part of this assignment – we will cover this in brief overview in lecture, you will need to provide some additional external research on your own to complete this assignment.

Below is the output of what your program should display when executed:

1. Load Data (From File)

2. Exit Program

Please enter your selection: 1

Unsorted Array: 39, 14, 100, 16, 93, 24, 62, 68, 52, 76, 86, 48, 15, 41, 83, 55, 18, 30, 74, 7, 31, 44, 67, 81, 70, 27, 53, 59, 61, 19, 56, 35, 88, 58, 72, 98, 38, 64, 94, 69, 50, 46, 78, 6, 57, 89, 26, 20, 79, 49

1. Insertion Sort

2. Bubble Sort

3. Exit Program

Please enter your selection: 1

Insertion Sort: 6, 7, 14, 15, 16, 18, 19, 20, 24, 26, 27, 30, 31, 35, 38, 39, 41, 44, 46, 48, 49, 50, 52, 53, 55, 56, 57, 58, 59, 61, 62, 64, 67, 68, 69, 70, 72, 74, 76, 78, 79, 81, 83, 86, 88, 89, 93, 94, 98, 100

1. Load Data (From File)

2. Exit Program

Please enter your selection: 1

Unsorted Array: 39, 14, 100, 16, 93, 24, 62, 68, 52, 76, 86, 48, 15, 41, 83, 55, 18, 30, 74, 7, 31, 44, 67, 81, 70, 27, 53, 59, 61, 19, 56, 35, 88, 58, 72, 98, 38, 64, 94, 69, 50, 46, 78, 6, 57, 89, 26, 20, 79, 49

1. Insertion Sort

2. Bubble Sort

3. Exit Program

Please enter your selection: 2

Bubble Sort: 6, 7, 14, 15, 16, 18, 19, 20, 24, 26, 27, 30, 31, 35, 38, 39, 41, 44, 46, 48, 49, 50, 52, 53, 55, 56, 57, 58, 59, 61, 62, 64, 67, 68, 69, 70, 72, 74, 76, 78, 79, 81, 83, 86, 88, 89, 93, 94, 98, 100

1. Load Data (From File)

2. Exit Program

Please enter your selection: 2

Goodbye!

Answer 1

abc

package abc1;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class FileSorting {
   private static final String FILENAME = "C:\\Users\\cr\\Desktop\\data22.txt";
   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;
   }
   }
   private static int[] loadInteger() throws NumberFormatException, IOException{
       ArrayList<Integer> rows = new ArrayList<Integer>();
       int [] list=new int[50];
   BufferedReader reader = new BufferedReader(new FileReader(FILENAME));

   String s;
   while((s = reader.readLine())!=null)
   {
       String[]wordlist=s.split(",");
       for(int i=0;i<wordlist.length;i++){
           rows.add(Integer.parseInt(wordlist[i]));
           list[i]=Integer.parseInt(wordlist[i]);
           System.out.println(list[i]);
       }
      
   }
     

  
   reader.close();
   return list;

   }
   static void bubbleSort(int[] arr) {
int n = arr.length;
int temp = 0;
for(int i=0; i < n; i++){
for(int j=1; j < (n-i); j++){
if(arr[j-1] > arr[j]){
//swap elements
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
  
}
}
for(int i=0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
  
}
public static void main(String[] args) throws IOException {
   int choice;
   Scanner scan=new Scanner(System.in);
   System.out.println("enter your choice ");
   choice=scan.nextInt();
   if(choice==1){
       int[] list=loadInteger();
       int choice2=scan.nextInt();
       if(choice2==1){
           insertionSort(list);
       }
       else if(choice2==2){
           bubbleSort(list);
       }
       else{
           System.out.println("bye");
          
       }
   }
  
   else{
       System.out.println("bye");
   }
   }
}