For assignment 5, you will be writing a sort for the words in a provided diction

Question

For assignment 5, you will be writing a sort for the words in a provided dictionary file of 235,886 entries.

I have already written the code to read in the file (assn5data.txt) as an ArrayList and also store it as an Array of Strings. One of the two structures will probably be useful for the sort that you will write.

The Given Code: https://drive.google.com/open?id=1_5r6NNU0fRDDl7bZNRu1DBWJxDIHEkV5ENCHNvftDRQ

I used the ArrayList to run the built-in Java “Collections.sort”.

I use the Array or Strings to run the Selection Sort that I provided.

I am providing the code to do nearly everything except what is asked for below.

For your part:

1.) Change the file name to match the location of the assn5data.txt file on your system

2.) Add another method to perform another sort of your choosing

3.) Call your sort method from the third sort section within the “callSortandTime” method

4.) Comment everything really well

5.) See if you can beat the timing of the other two sorts, but note that it may be very difficult to beat the timing of the built-in Java sort.

TextFile: https://drive.google.com/open?id=1S1xgv7apoXkd0jabgLyMBh66BTXCQabL2Aa0-pBGaJA

Explanation / Answer

// Here you go. Code has been tested. Used QuickSort :)
// It's average case time is same as mergesort, but the advantage is that it doesn't require huge memory like mergesort :) And QSort is always prefered for practical purposes over mergesort.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
import java.time.*;
import java.util.Collections;

public class Assn5jonesjo {
  
   // the arraylist is used for ...
    private ArrayList<String> dict = new ArrayList<String>();
    private String[] stockArr; // A 'regular' string array
    private String inFile="/Users/john/assn5dict.txt";   // Change this to match your dictionary file path

    public void readInFile()
    {
        File myFile = new File(this.inFile);
        String str1;
        // Use a "try..catch" safety net when working with files
        try {
              // Instantiate and open "readFile"
              Scanner readFile = new Scanner(myFile);
              // Read the first three lines in
              while (readFile.hasNext())
              {
                str1=readFile.nextLine(); // read the string in from the file
                dict.add(str1); // add each string to our dict ArrayList
              }
              // close the file when finished
             readFile.close();
         }
         catch (FileNotFoundException e) {
                e.printStackTrace();
         }    
    }
  
    public static <T extends Comparable<? super T>> void shellsort( T [ ] a )
    {
        // This is a Shell Sort algorithm
        int j;
        for( int gap = a.length / 2; gap > 0; gap /= 2 )
        {
          for( int i = gap; i < a.length; i++ )
          {
             T tmp = a[ i ];
             for( j = i; j >= gap && tmp.compareTo( a[ j - gap ] ) < 0; j -= gap )
             {
               a[ j ] = a[ j - gap ];
             }
             a[ j ] = tmp;
          }
        }
    }
  
  
   /**
   * QuickSort with Hoare's Scheme
   * @param <T>
   */
   public static <T extends Comparable<? super T>> void qSortHoare( T [] arr, int low, int high) {
       if (low < high) {
           int pi = partitionHoare(arr, low, high);
           qSortHoare(arr, low, pi);
           qSortHoare(arr, pi + 1, high);
       }
   }

   public static <T extends Comparable<? super T>> int partitionHoare(T[] arr, int low, int high) {
       T pivot = arr[low];
       int i = low - 1, j = high + 1;

       while (true) {
           do {
               i++;
           } while (pivot.compareTo(arr[i]) > 0);

           do {
               j--;
           } while (pivot.compareTo(arr[j]) < 0);

           if (i >= j) {
               return j;
           }

           /* Swap A[i] and A[j] */  
           T temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
       }
   }
  
   // this method displays the first x items in the dictionary list
   public void showfirstX(int x, boolean isList) {
       if (isList) {
           for (int y = 0; y < x; y++) {
               System.out.println(y + " " + this.dict.get(y));
           }
       } else
           for (int y = 0; y < x; y++) {
               System.out.println(y + " " + stockArr[y]);
           }
   }

    // Does exactly as the name implies, calls a sort and also times it
    public void callSortandTime(int sortNumber)
    {
      Instant before, after; // set up variables for timing
      long delta;             // another variable for timing
      before = Instant.now(); // Get time before running something
      // measure what happens until the "after" line

      if (sortNumber == 1)
      {
        // Sort 1 is the built-in collections.sort
        // Which is likely to be a merge sort for a large number of items
        // but this can vary with different versions of Java
        Collections.sort(this.dict);
      }
      else if (sortNumber == 2)
      {
        // Sort 2 is a "shell sort" that I borrowed from a book.
          Assn5jonesjo.shellsort(this.stockArr);
      }
      else if (sortNumber == 3)
      {
        Assn5jonesjo.qSortHoare(this.stockArr, 0, stockArr.length-1);
      }
      after = Instant.now(); // Get time after running something
      delta = Duration.between(before, after).toMillis();
      System.out.println("Sort "+sortNumber+" took "+delta+" ms");
    }
  
    public static void main(String[] args) {

      ArrayList<String> Save = new ArrayList<String>();
      // instantiate an object of your own class
      // Don't forget to change it to your own pirateID!
      Assn5jonesjo dictionary = new Assn5jonesjo();

      dictionary.readInFile(); // Read the dictionary file into an ArrayList
      dictionary.showfirstX(5, true); // Show some of the list to see if it is (un)sorted
    
        // Save a copy of the ArrayList before doing any sorting
      Save.addAll(dictionary.dict);
    
      // Run the first sort - a built-in Java sort
      dictionary.callSortandTime(1); // pass a 1 to run sort #1
      // Show the partial results
      dictionary.showfirstX(5,true);

      // Put the dictionary back to an unsorted list
      dictionary.dict.clear();
      dictionary.dict.addAll(Save); // Put the saved ArrayList back before the next sort
      System.out.println("Back to unsorted:");
      dictionary.showfirstX(5, true);
    
      // convert ArrayList to string array for the next sort
      dictionary.stockArr = dictionary.dict.toArray(new String[dictionary.dict.size()]);

      // sort 2 here
      dictionary.callSortandTime(2); // pass a 2 to run sort #2
      dictionary.showfirstX(5, false);

      dictionary.dict.clear();
      dictionary.dict.addAll(Save); // Put the saved ArrayList back before the next sort

      // Call the third sort - don't forget to write the third sort
      dictionary.callSortandTime(3);
      dictionary.showfirstX(5, false);
    
    }

}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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