Question

java

Introduction:	Runtime complexity is an issue when determining which algorithms we should use. Some algorithms are easy to implement but run too slowly to be useful. Knowing the advantages and disadvantages of different algorithms helps in determining the best solution to a problem.
Description:	You are to implement two different sorting algorithms and count the number of steps involved with the sort routine (the comparisons and moving positions). Every time a comparison or move is made you should count it. You have been given a data file with text. You must read through the file to determine the number of words in it, then create an array big enough to hold the values. Once the array is built you need to reread the file to store the strings into the array. You must implement Insertion Sort and Quick Sort. These sorts must take an array of strings and sort them in ascending order. When sorted you must display each UNIQUE value and the number of times it appears in the array. At the end you must print out which sort was used and how many steps it took to complete. You must keep asking the user which sort to use until the Exit symbol is entered. Remember that passing an array to a method will modify the original array. You must copy the array so you do not lose the order of the original and just sort the copy.
Program:	You must create a program called p6.java. Everything can be done inside of this file if done within the same class. If you wish to create additional classes to help, you must have them in separate .java files.
Input:	There is an input file called p6.dat were each line contains a name.

p6.dat content:

I AM SAM. I AM SAM. SAM-I-AM. THAT SAM-I-AM! THAT SAM-I-AM! I DO NOT LIKE THAT SAM-I-AM! DO WOULD YOU LIKE GREEN EGGS AND HAM? I DO NOT LIKE THEM,SAM-I-AM. I DO NOT LIKE GREEN EGGS AND HAM. WOULD YOU LIKE THEM HERE OR THERE? I WOULD NOT LIKE THEM HERE OR THERE. I WOULD NOT LIKE THEM ANYWHERE. I DO NOT LIKE GREEN EGGS AND HAM. I DO NOT LIKE THEM, SAM-I-AM. WOULD YOU LIKE THEM IN A HOUSE? WOULD YOU LIKE THEN WITH A MOUSE? I DO NOT LIKE THEM IN A HOUSE. I DO NOT LIKE THEM WITH A MOUSE. I DO NOT LIKE THEM HERE OR THERE. I DO NOT LIKE THEM ANYWHERE. I DO NOT LIKE GREEN EGGS AND HAM. I DO NOT LIKE THEM, SAM-I-AM. WOULD YOU EAT THEM IN A BOX? WOULD YOU EAT THEM WITH A FOX? NOT IN A BOX. NOT WITH A FOX. NOT IN A HOUSE. NOT WITH A MOUSE. I WOULD NOT EAT THEM HERE OR THERE. I WOULD NOT EAT THEM ANYWHERE. I WOULD NOT EAT GREEN EGGS AND HAM. I DO NOT LIKE THEM, SAM-I-AM. WOULD YOU? COULD YOU? IN A CAR? EAT THEM! EAT THEM! HERE THEY ARE. I WOULD NOT, COULD NOT, IN A CAR. YOU MAY LIKE THEM. YOU WILL SEE. YOU MAY LIKE THEM IN A TREE! I WOULD NOT, COULD NOT IN A TREE. NOT IN A CAR! YOU LET ME BE. I DO NOT LIKE THEM IN A BOX. I DO NOT LIKE THEM WITH A FOX. I DO NOT LIKE THEM IN A HOUSE. I DO NOT LIKE THEM WITH A MOUSE. I DO NOT LIKE THEM HERE OR THERE. I DO NOT LIKE THEM ANYWHERE. I DO NOT LIKE GREEN EGGS AND HAM. I DO NOT LIKE THEM, SAM-I-AM. A TRAIN! A TRAIN! A TRAIN! A TRAIN! COULD YOU, WOULD YOU ON A TRAIN? NOT ON TRAIN! NOT IN A TREE! NOT IN A CAR! SAM! LET ME BE! I WOULD NOT, COULD NOT, IN A BOX. I WOULD NOT, COULD NOT, WITH A FOX. I WILL NOT EAT THEM IN A HOUSE. I WILL NOT EAT THEM HERE OR THERE. I WILL NOT EAT THEM ANYWHERE. I DO NOT EAT GREEM EGGS AND HAM. I DO NOT LIKE THEM, SAM-I-AM. SAY! IN THE DARK? HERE IN THE DARK! WOULD YOU, COULD YOU, IN THE DARK? I WOULD NOT, COULD NOT, IN THE DARK. WOULD YOU COULD YOU IN THE RAIN? I WOULD NOT, COULD NOT IN THE RAIN. NOT IN THE DARK. NOT ON A TRAIN. NOT IN A CAR. NOT IN A TREE. I DO NOT LIKE THEM, SAM, YOU SEE. NOT IN A HOUSE. NOT IN A BOX. NOT WITH A MOUSE. NOT WITH A FOX. I WILL NOT EAT THEM HERE OR THERE. I DO NOT LIKE THEM ANYWHERE! YOU DO NOT LIKE GREEN EGGS AND HAM? I DO NOT LIKE THEM, SAM-I-AM. COULD YOU, WOULD YOU, WITH A GOAT? I WOULD NOT, COULD NOT WITH A GOAT! WOULD YOU, COULD YOU, ON A BOAT? I COULD NOT, WOULD NOT, ON A BOAT. I WILL NOT, WILL NOT, WITH A GOAT. I WILL NOT EAT THEM IN THE RAIN. NOT IN THE DARK! NOT IN A TREE! NOT IN A CAR! YOU LET ME BE! I DO NOT LIKE THEM IN A BOX. I DO NOT LIKE THEM WITH A FOX. I WILL NOT EAT THEM IN A HOUSE. I DO NOT LIKE THEM WITH A MOUSE. I DO NOT LIKE THEM HERE OR THERE. I DO NOT LIKE THEM ANYWHERE! I DO NOT LIKE GREEN EGGS AND HAM! I DO NOT LIKE THEM, SAM-I-AM. YOU DO NOT LIKE THEM. SO YOU SAY. TRY THEM! TRY THEM! AND YOU MAY. TRY THEM AND YOU MAY, I SAY. SAM! IF YOU LET ME BE, I WILL TRY THEM. YOU WILL SEE. SAY! I LIKE GREEN EGGS AND HAM! I DO! I LIKE THEM, SAM-I-AM! AND I WOULD EAT THEM IN A BOAT. AND I WOULD EAT THEM WITH A GOAT... AND I WILL EAT THEM, IN THE RAIN. AND IN THE DARK. AND ON A TRAIN. AND IN A CAR. AND IN A TREE. THEY ARE SO GOOD, SO GOOD, YOU SEE! SO I WILL EAT THEM IN A BOX. AND I WILL EAT THEM WITH A FOX. AND I WILL EAT THEM IN A HOUSE. AND I WILL EAT THEM WITH A MOUSE. AND I WILL EAT THEM HERE AND THERE. SAY! I WILL EAT THEM ANYWHERE! I DO SO LIKE GREEN EGGS AND HAM! THANK YOU! THANK YOU, SAM-I-AM.

Output:	(S)election Sort (Q)uick Sort (E)xit Enter choice: Q A : 56 frequency. AM : 2 frequency. AND : 25 frequency. ANYWHERE! : 3 frequency. ANYWHERE. : 5 frequency. ARE : 1 frequency. ARE. : 1 frequency. BE! : 2 frequency. BE, : 1 frequency. BE. : 1 frequency. BOAT. : 2 frequency. BOAT? : 1 frequency. BOX. : 6 frequency. BOX? : 1 frequency. CAR! : 3 frequency. CAR. : 3 frequency. CAR? : 1 frequency. COULD : 14 frequency. DARK! : 2 frequency. DARK. : 3 frequency. DARK? : 2 frequency. DO : 36 frequency. DO! : 1 frequency. EAT : 23 frequency. EGGS : 11 frequency. FOX. : 6 frequency. FOX? : 1 frequency. GOAT! : 1 frequency. GOAT. : 1 frequency. GOAT... : 1 frequency. GOAT? : 1 frequency. GOOD, : 2 frequency. GREEM : 1 frequency. GREEN : 10 frequency. HAM! : 3 frequency. HAM. : 6 frequency. HAM? : 2 frequency. HERE : 11 frequency. HOUSE. : 7 frequency. HOUSE? : 1 frequency. I : 69 frequency. IF : 1 frequency. IN : 40 frequency. LET : 4 frequency. LIKE : 44 frequency. MAY : 2 frequency. MAY, : 1 frequency. MAY. : 1 frequency. ME : 4 frequency. MOUSE. : 6 frequency. MOUSE? : 1 frequency. NOT : 67 frequency. NOT, : 15 frequency. ON : 6 frequency. OR : 8 frequency. RAIN. : 3 frequency. RAIN? : 1 frequency. SAM! : 2 frequency. SAM, : 1 frequency. SAM-I-AM! : 4 frequency. SAM-I-AM. : 9 frequency. SAM. : 2 frequency. SAY! : 3 frequency. SAY. : 2 frequency. SEE! : 1 frequency. SEE. : 3 frequency. SO : 5 frequency. THANK : 2 frequency. THAT : 3 frequency. THE : 11 frequency. THEM : 40 frequency. THEM! : 4 frequency. THEM, : 10 frequency. THEM,SAM-I-AM. : 1 frequency. THEM. : 3 frequency. THEN : 1 frequency. THERE. : 8 frequency. THERE? : 1 frequency. THEY : 2 frequency. TRAIN! : 5 frequency. TRAIN. : 2 frequency. TRAIN? : 1 frequency. TREE! : 3 frequency. TREE. : 3 frequency. TRY : 4 frequency. WILL : 18 frequency. WITH : 18 frequency. WOULD : 27 frequency. YOU : 23 frequency. YOU! : 1 frequency. YOU, : 8 frequency. YOU? : 2 frequency. Quicksort finished in 12000 steps.
Hints:	Note that depending on implementation the number of steps you will have is different from others. Use appropriate software design techniques, and implement the class methods with Java constructs for I/O, declarations, and calculations. Build your program in steps (i.e., get the input and output working, then add the functions, etc.). Emphasize functionality first, then add the advanced features.
data:	Remember that you must pass the data file name in as a command line argument.

Answer 1

package string;

import java.io.*;
import java.util.*;

// Defines class FileWordFrequencySort
public class FileWordFrequencySort
{
   // Creates an array list to store words read from file
   ArrayList<String> allWords = new ArrayList<String>();
   // To store unique words
   String[] uniqueWords;
   // To store frequency of each word
   int [] frequencyWord;
   // To count steps required for sorting
   int count;
  
   // Method to read file contents and store the words in the array list
   void readFile()
   {
       // Scanner class object created
       Scanner sc = new Scanner(System.in);
       // Scanner class object declared to read file contents
       Scanner fileRead = null;
      
       // To store a line read from file
       String line;
       // To store file name
       String fileName = "p6.dat";      
      
       // try block begins
       try
       {
           // Opens the file for reading
           fileRead = new Scanner(new File(fileName));
          
           // Loops till end of the file
           while(fileRead.hasNextLine())
           {
               // Reads a line from the file
               line = fileRead.nextLine();
              
               // Checks if blank line then continue the loop
               if(line.length() == 0)
                   continue;
               // Removes the extra space before and after the line
               line = line.trim();
              
               // Split the line with space and stores it in words array
               String words[] = line.split("\\s+");
              
               // Loops till end of the words array
               for(int c = 0; c < words.length; c++)
                   // Adds each word to array list allWordsWord
                   allWords.add(words[c]);
           }// End of while loop
          
           // Close the file
           fileRead.close();
       }// End of try
      
       // Catch block to handle FileNotFoundException
       catch (FileNotFoundException e)
       {
           e.printStackTrace();
           System.err.println("Unable to open the file: " + fileName);
       }// End of catch      
   }// End of method
  
   // Method to return unique words array
   private String[] getUniqueWords()
{
       // Creates a string array to store unique words
String[] uniqueWords = new String[allWords.size()];
// Stores the first word
uniqueWords[0] = allWords.get(0);
// Sets the unique index to 1
int uniqueIndex = 1;

// Boolean variable to store word found status
boolean wordFound = false;
  
// Loops from 1 index position to end of the array lists
for(int c = 1; c < allWords.size(); c++)
{
// Loops from 0th index position to current length of uniqueWords
   for(int d = 0; d <= uniqueIndex; d++)
       // Checks if c index position of all words (array list)
       // is equals to d index position of unique words
if(allWords.get(c).equals(uniqueWords[d]))
   // Sets the word status to true for found
wordFound = true;

   // Checks if word found status to not true
if(!wordFound)
{
   // Stores the c index position word of all words
   // at uniqueIndex position of unique words
   uniqueWords[uniqueIndex] = allWords.get(c);
   // Increase the unique index by one
uniqueIndex++;
}// End of if condition
  
// Resets the word found status to false for next word
wordFound = false;
}// End of for loop
  
// Crates a temporary string array of size uniqueIndex
String[] finalUniqueWords = new String[uniqueIndex];
// Loops till number of words in uniqueWords
for(int c = 0; c < uniqueIndex; c++)
   // Assigns each word
   finalUniqueWords[c] = uniqueWords[c];
// Returns the final unique words array
return finalUniqueWords;
}// End of method

   // Method to calculate frequency
   void getFrequency()
   {
       // Calls the method to get unique word array
       uniqueWords = getUniqueWords();
       // Allocate memory of size unique word length
       frequencyWord = new int[uniqueWords.length];
       int index = 0;
      
       // Loops till end of the unique word
       for(String uniqueW: uniqueWords)
{
           // Sets the counter to 0 for each word
           int counter = 0;
           // Checks if current unique word is null then come out of the loop
if(null == uniqueW)
   break;
// Loops till end of the all words
for(String allW : allWords)
   // Checks if current unique word is equals to current all word
if(uniqueW.equals(allW))
   // Increase the counter by one
   counter++;   
// Assigns the counter value at index position of frequency word array
frequencyWord[index++] = counter;
}// End of for loop
   }// End of method
  
   // Method for selection sort and returns number of steps taken
   int selectionSort()
   {
       count = 0;          
       // One by one move boundary of unsorted sub-array
       for (int i = 0; i < uniqueWords.length - 1; i++)
       {
           // Stores the current value or i as the minimum index position
           int minIndex = i;
           // Loops till length minus one time
           for (int j = i + 1; j < uniqueWords.length-1; j++)
           {
               // Checks if the j index position value is less than the minIndex position value
               if (uniqueWords[j].compareTo(uniqueWords[minIndex]) < 0)
                   // Set the j value as the minimum index position
                   minIndex = j;
               count++;
           }
           // Swapping process
           String tempW = uniqueWords[minIndex];
           uniqueWords[minIndex] = uniqueWords[i];
           uniqueWords[i] = tempW;
          
           // Swapping process
           int tempF = frequencyWord[minIndex];
           frequencyWord[minIndex] = frequencyWord[i];
           frequencyWord[i] = tempF;
       }// End of for loop
       return count;
   }// End of method
  
   /* Method takes last element as pivot, places the pivot element at its correct position in sorted array, and places all
   smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */
   public int partition(String uniqueWords[], int low, int high)
   {
       String pivot = uniqueWords[high];
       // index of smaller element
       int i = (low-1);
      
       //   Loops till low is less than high
       for (int c = low; c < high; c++)
       {
           count++;
           // If current element is smaller than or equal to pivot
           if (uniqueWords[c].compareTo(pivot) <= 0)
           {
               count++;
               i++;
               // Swap uniqueWords[i] and uniqueWords[c]
               String tempW = uniqueWords[i];
               uniqueWords[i] = uniqueWords[c];
               uniqueWords[c] = tempW;
              
               // Swap frequencyWord[i] and frequencyWord[c]
               int tempF = frequencyWord[i];
               frequencyWord[i] = frequencyWord[c];
               frequencyWord[c] = tempF;
           }//End of if
       }//End of for

       // Swap uniqueWords[i+1] and uniqueWords[high] (or pivot)
       String tempW = uniqueWords[i+1];
       uniqueWords[i+1] = uniqueWords[high];
       uniqueWords[high] = tempW;
      
       // Swap frequencyWord[i+1] and frequencyWord[high] (or pivot)
       int tempF = frequencyWord[i+1];
       frequencyWord[i+1] = frequencyWord[high];
       frequencyWord[high] = tempF;
      
       return i + 1;
   }//End of method
  
   // Method that implements QuickSort()
   public int quickSort(String uniqueWords[], int low, int high)
   {
       if (low < high)
       {
           // part is partitioning index, uniqueWords[part] is now at right place
           int part = partition(uniqueWords, low, high);
           count++;
           // Recursively sort elements before partition and after partition
           quickSort(uniqueWords, low, part-1);
           count++;
           quickSort(uniqueWords, part+1, high);
       }//End of if
       return count;
   }// End of method
  
   // Method to display the word and its frequency
   void show()
   {
       // Loops till end of the unique words
       for(int c = 0; c < uniqueWords.length; c++)
           // Displays current word and its frequency
           System.out.println(uniqueWords[c] + ": " + frequencyWord[c] + " frequency.");
   }// End of method
  
   // main method definition
   public static void main(String []s)
   {
       int count;
       char choice;
       Scanner sc = new Scanner(System.in);
      
       // Creates an object of class FileWordFrequencySort
       FileWordFrequencySort fw = new FileWordFrequencySort();

       // Calls the method to read file contents      
       fw.readFile();          
       // Calls the method to count each word frequency
       fw.getFrequency();
      
       // Loops till user choice is not "Q" or "q"
       do
       {
           // Displays menu
           System.out.print("\n (S)election Sort \n (Q)uick Sort \n (E)xit " +
                   "\n Enter choice: ");
           // Accepts user choice
           choice = sc.next().charAt(0);
          
           // Checks user choice and calls appropriate method
           switch(choice)
           {
               case 'S':
               case 's':
                   count = fw.selectionSort();
                   fw.show();
                   System.out.println("\n Selection sort finished in " + count + " steps.");
               break;
               case 'Q':
               case 'q':
                   count = fw.quickSort(fw.uniqueWords, 0, fw.uniqueWords.length-1);
                   fw.show();
                   System.out.println("\n Quick sort finished in " + count + " steps.");
               break;              
               case 'E':
               case 'e':
                   System.exit(0);
               default:
                   System.out.println("\n Invalid choice!!");
           }// End of switch - case
       }while(true);// End of do - while loop
   }// End of main method
}// End of class

Sample Output:

(S)election Sort
(Q)uick Sort
(E)xit
Enter choice: y

Invalid choice!!

(S)election Sort
(Q)uick Sort
(E)xit
Enter choice: s
A: 56 frequency.
AM: 2 frequency.
AND: 25 frequency.
ANYWHERE!: 3 frequency.
ANYWHERE.: 5 frequency.
ARE: 1 frequency.
ARE.: 1 frequency.
BE!: 2 frequency.
BE,: 1 frequency.
BE.: 1 frequency.
BOAT.: 2 frequency.
BOAT?: 1 frequency.
BOX.: 6 frequency.
BOX?: 1 frequency.
CAR!: 3 frequency.
CAR.: 3 frequency.
CAR?: 1 frequency.
COULD: 14 frequency.
DARK!: 2 frequency.
DARK.: 3 frequency.
DARK?: 2 frequency.
DO: 36 frequency.
DO!: 1 frequency.
EAT: 23 frequency.
EGGS: 11 frequency.
FOX.: 6 frequency.
FOX?: 1 frequency.
GOAT!: 1 frequency.
GOAT.: 1 frequency.
GOAT...: 1 frequency.
GOAT?: 1 frequency.
GOOD,: 2 frequency.
GREEM: 1 frequency.
GREEN: 10 frequency.
HAM!: 3 frequency.
HAM.: 6 frequency.
HAM?: 2 frequency.
HERE: 11 frequency.
HOUSE.: 7 frequency.
HOUSE?: 1 frequency.
I: 69 frequency.
IF: 1 frequency.
IN: 40 frequency.
LET: 4 frequency.
LIKE: 44 frequency.
MAY: 2 frequency.
MAY,: 1 frequency.
MAY.: 1 frequency.
ME: 4 frequency.
MOUSE.: 6 frequency.
MOUSE?: 1 frequency.
NOT: 67 frequency.
NOT,: 15 frequency.
ON: 6 frequency.
OR: 8 frequency.
RAIN.: 3 frequency.
RAIN?: 1 frequency.
SAM!: 2 frequency.
SAM,: 1 frequency.
SAM-I-AM!: 4 frequency.
SAM-I-AM.: 9 frequency.
SAM.: 2 frequency.
SAY!: 3 frequency.
SAY.: 2 frequency.
SEE!: 1 frequency.
SEE.: 3 frequency.
SO: 5 frequency.
THANK: 2 frequency.
THAT: 3 frequency.
THE: 11 frequency.
THEM: 40 frequency.
THEM!: 4 frequency.
THEM,: 10 frequency.
THEM,SAM-I-AM.: 1 frequency.
THEM.: 3 frequency.
THEN: 1 frequency.
THERE.: 8 frequency.
THERE?: 1 frequency.
THEY: 2 frequency.
TRAIN!: 5 frequency.
TRAIN.: 2 frequency.
TRAIN?: 1 frequency.
TREE!: 3 frequency.
TREE.: 3 frequency.
TRY: 4 frequency.
WILL: 18 frequency.
WITH: 18 frequency.
WOULD: 27 frequency.
YOU: 23 frequency.
YOU,: 8 frequency.
YOU?: 2 frequency.
YOU!: 1 frequency.

Selection sort finished in 4095 steps.

(S)election Sort
(Q)uick Sort
(E)xit
Enter choice: q
A: 56 frequency.
AM: 2 frequency.
AND: 25 frequency.
ANYWHERE!: 3 frequency.
ANYWHERE.: 5 frequency.
ARE: 1 frequency.
ARE.: 1 frequency.
BE!: 2 frequency.
BE,: 1 frequency.
BE.: 1 frequency.
BOAT.: 2 frequency.
BOAT?: 1 frequency.
BOX.: 6 frequency.
BOX?: 1 frequency.
CAR!: 3 frequency.
CAR.: 3 frequency.
CAR?: 1 frequency.
COULD: 14 frequency.
DARK!: 2 frequency.
DARK.: 3 frequency.
DARK?: 2 frequency.
DO: 36 frequency.
DO!: 1 frequency.
EAT: 23 frequency.
EGGS: 11 frequency.
FOX.: 6 frequency.
FOX?: 1 frequency.
GOAT!: 1 frequency.
GOAT.: 1 frequency.
GOAT...: 1 frequency.
GOAT?: 1 frequency.
GOOD,: 2 frequency.
GREEM: 1 frequency.
GREEN: 10 frequency.
HAM!: 3 frequency.
HAM.: 6 frequency.
HAM?: 2 frequency.
HERE: 11 frequency.
HOUSE.: 7 frequency.
HOUSE?: 1 frequency.
I: 69 frequency.
IF: 1 frequency.
IN: 40 frequency.
LET: 4 frequency.
LIKE: 44 frequency.
MAY: 2 frequency.
MAY,: 1 frequency.
MAY.: 1 frequency.
ME: 4 frequency.
MOUSE.: 6 frequency.
MOUSE?: 1 frequency.
NOT: 67 frequency.
NOT,: 15 frequency.
ON: 6 frequency.
OR: 8 frequency.
RAIN.: 3 frequency.
RAIN?: 1 frequency.
SAM!: 2 frequency.
SAM,: 1 frequency.
SAM-I-AM!: 4 frequency.
SAM-I-AM.: 9 frequency.
SAM.: 2 frequency.
SAY!: 3 frequency.
SAY.: 2 frequency.
SEE!: 1 frequency.
SEE.: 3 frequency.
SO: 5 frequency.
THANK: 2 frequency.
THAT: 3 frequency.
THE: 11 frequency.
THEM: 40 frequency.
THEM!: 4 frequency.
THEM,: 10 frequency.
THEM,SAM-I-AM.: 1 frequency.
THEM.: 3 frequency.
THEN: 1 frequency.
THERE.: 8 frequency.
THERE?: 1 frequency.
THEY: 2 frequency.
TRAIN!: 5 frequency.
TRAIN.: 2 frequency.
TRAIN?: 1 frequency.
TREE!: 3 frequency.
TREE.: 3 frequency.
TRY: 4 frequency.
WILL: 18 frequency.
WITH: 18 frequency.
WOULD: 27 frequency.
YOU: 23 frequency.
YOU!: 1 frequency.
YOU,: 8 frequency.
YOU?: 2 frequency.

Quick sort finished in 12288 steps.

(S)election Sort
(Q)uick Sort
(E)xit
Enter choice: e