You may use the LinkedList and ArrayList classes that are included in the JDK fo

Question

You may use the LinkedList and ArrayList classes that are included in the JDK for this assignment; you do not have to code your own list classes.

Test binary search with an array, an array list, and a linked list. Write code to do the following:

1. Read a text file, parse it to individual words, and separately save the words to an array, an array list, and a linked list. Many of the words will be duplicates; for example, "the" will likely appear multiple times if you read a large text file written in English. The best way to find the size of the array to create is to save to the lists first, then check the size of one of the lists.

2. Code any type of sort you choose twice, one for an array and once for a list. If you have studied recursion, use quicksort; if not, insertion sort is probably the best choice. If the method takes a List as parameter, you can use the same code to sort and array list and a linked list.

3. Code binary search twice; once for an array and once for a list.

4. Adapt the Stopwatch code from the lecture to test and print out the time in milliseconds it takes to sort the array and each of the two lists (after a file has already been read) and to find and print out the time in milliseconds it takes to use binary search to see if the array and each of the two lists contains an arbitrary word taken from user input.

Explanation / Answer

import java.io.FileNotFoundException; import java.io.FileReader; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Solution { int binary_search_list(List list, String x) { //binary search for list int l = 0, r = list.size() - 1, mid; while (l 0) r = mid - 1; else l = mid + 1; } return -1; } int binary_search_array(String[] arr, String x) { //binary search for array int l = 0, r = arr.length - 1, mid; while (l 0) r = mid - 1; else l = mid + 1; } return -1; } void sort_array(String[] arr) { //insertion implementation for array int n = arr.length; for (int i = 1; i = 0 && temp.compareTo(arr[j]) < 0) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } } void sort_list(List arr) { //insertion implementation for list int n = arr.size(); for (int i = 1; i = 0 && temp.compareTo(arr.get(j)) < 0) { arr.set(j + 1, arr.get(j)); j--; } arr.set(j + 1, temp); } } public static void main(String[] args) { Solution o = new Solution(); StringBuilder sb = new StringBuilder(); // store file data Scanner sc = null; try { //opening and reading from file sc = new Scanner(new FileReader("Please put filename here")); while (sc.hasNext()) { sb.append(sc.nextLine()); } } catch (FileNotFoundException e) { // if file not found then throw an exception e.printStackTrace(); } finally { // closing after done sc.close(); } String s = sb.toString(); List list = new ArrayList(); String[] arr = s.split(" "); //spliting file data into words for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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