You will see the program is set up as a single Java file including 2 classes, Ar
ID: 3547418 • Letter: Y
Question
You will see the program is set up as a single Java file including 2 classes, ArrayList and a public Lab5A with the main method. Leave it as one file. Add your name inside the existing header comment block at the top of that file.
The ArrayList class includes sequentialSearch(), sortedSearch(), and binarySearch() methods. There is also a main() to demonstrate how the search methods are used. The ArrayList class also includes all of the sorting methods from the previous assignment. Completely rewrite the main program so that times for all three methods are displayed. Also as previously, use System.currentTimeMillis() method before and after the search to calculate the search times.
Time the three search methods for several large list lengths, filling the array lists with random integer between 0 and 999. Search for a random integer in the same range, and all three searches should search for the same target. Sort the list using any of the methods provided between the Sequential and the Sorted searches. Use at least 6 different list lengths. Create a table to record the times.
import java.util.*;
// Class implementing an array based list. Sequential search,
// sorted search, and binary search algorithms are implemented also
class ArrayList
{
private static int SIZE; //size of the array that stores the list items
private int[] list; //array to store the list items
private int length; //amount of items in the list
// Default constructor.
public ArrayList()
{
SIZE = 20;
list = new int[SIZE];
length = 0;
}
// Determines whether the list is empty
public boolean isEmpty()
{
return length == 0;
}
// Prints the list elements.
public void display()
{
for (int i = 0; i < length; i++)
System.out.print(list[i] + " ");
System.out.println();
}
// Adds the element x to the end of the list
public void add(int x)
{
if (length == SIZE)
System.out.println("Insertion Error: list is full");
else
{
list[length] = x;
length++;
}
}
// Removes the element at the given location from the list
public void removeAt(int pos)
{
for (int i = pos; i < length - 1; i++)
list[i] = list[i + 1];
length--;
}
// One argument constructor
public ArrayList(int size)
{
SIZE = size;
list = new int[SIZE];
length = 0;
}
// Returns the number of items in the list
public int getLength()
{
return length;
}
// Returns the size of the list (accessor method)
public int getSize()
{
return SIZE;
}
// Removes all of the items from the list.
public void clear()
{
length = 0;
}
// Replaces the item in the list at the position specified by location
public void replace(int location, int item)
{
if (location < 0 || location >= length)
System.out.println("Error: invalid location");
else
list[location] = item;
}
// Adds an item to the list at the position specified by location
public void add(int location, int item)
{
if (location < 0 || location >= length)
System.out.println("Error: invalid position");
else if (length == SIZE)
System.out.println("Error: Array is full");
else
{
for (int i = length; i > location; i--)
list[ i] = list[ i - 1];
list[location] = item;
length++;
}
}
// Deletes All occurrences of an item from the list
public void remove(int item)
{
for (int i = 0; i < length; i++)
if (list[i] == item)
{
removeAt(i);
i--; //onsecutive values must also removed; that's why i-- is here
}
}
// Returns the element at location
public int get(int location)
{
int x = -1;
if (location < 0 || location >= length)
System.out.println("Error: invalid location");
else
x = list[location];
return x;
}
// Makes a deep copy to another ArrayList object.
public ArrayList copy()
{
ArrayList newList = new ArrayList(this.SIZE);
newList.length = this.length;
for (int i = 0; i < length; i++)
newList.list[i] = this.list[i];
return newList;
}
// Bubble-sorts this ArrayList
public void bubbleSort()
{
for (int i = 0; i < length - 1; i++)
for (int j = 0; j < length - i - 1; j++)
if (list[j] > list[j + 1])
{
//swap list[j] and list[j+1]
int temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
}
}
// Quick-sorts this ArrayList.
public void quicksort()
{
quicksort(0, length - 1);
}
// Recursive quicksort algorithm.
private void quicksort(int begin, int end)
{
int temp;
int pivot = findPivotLocation(begin, end);
// swap list[pivot] and list[end]
temp = list[pivot];
list[pivot] = list[end];
list[end] = temp;
pivot = end;
int i = begin,
j = end - 1;
boolean iterationCompleted = false;
while (!iterationCompleted)
{
while (list[i] < list[pivot])
i++;
while ((j >= 0) && (list[pivot] < list[j]))
j--;
if (i < j)
{
//swap list[i] and list[j]
temp = list[i];
list[i] = list[j];
list[j] = temp;
i++;
j--;
} else
iterationCompleted = true;
}
//swap list[i] and list[pivot]
temp = list[i];
list[i] = list[pivot];
list[pivot] = temp;
if (begin < i - 1)
quicksort(begin, i - 1);
if (i + 1 < end)
quicksort(i + 1, end);
}
// Computes the pivot location.
private int findPivotLocation(int b, int e)
{
return (b + e) / 2;
}
// @return a string representation of the array list elements.
public String toString()
{
String s = "";
for (int i = 0; i < length; i++)
s += list[i] + " ";
return s;
}
// Determines if an item exists in the array list using sequential search
public boolean sequentialSearch(int x)
{
for (int i = 0; i < length; i++)
if (list[i] == x)
return true;
return false;
}
// Determines if an item exists in the array list using sorted search
// Note: List must be sorted
public boolean sortedSearch(int x)
{
//The list must ne sorted to invoke this method!
int i = 0;
while (i < length && list[i] < x)
i++;
if (i < length && list[i] == x)
return true; // x is in the array
else
return false; // x is not in the array
}
// Determines if an item exists in the array list using binary search
// Note: List must be sorted
public boolean binarySearch(int x)
{
int first = 0;
int last = length - 1;
int pivot;
boolean found = false;
while (first <= last && !found)
{
pivot = (first + last) / 2;
if (list[pivot] == x)
found = true;
else if (x < list[pivot])
last = pivot - 1;
else
first = pivot + 1;
}
if (found)
return true;
else
return false;
}
}
// Class to test sequential search, sorted search,
// and binary search algorithms implemented in ArrayList
public class Lab5A
{
public static void main(String[] args)
{
Lab5A myAppl = new Lab5A();
}
public Lab5A()
{
Scanner in = new Scanner(System.in);
//List creation and display
int n = 20;
ArrayList numbers = new ArrayList(n);
for (int i = 0; i < n; i++)
numbers.add((int) (Math.random() * 100));
System.out.println("List of integers:");
System.out.println(numbers);
//Searching with sequential search
System.out.print(" (Sequential Search) Enter a number:");
int x = in.nextInt();
if (numbers.sequentialSearch(x))
System.out.println("Found!");
else
System.out.println("Not found!");
//Sorting the list
numbers.quicksort();
System.out.println(" Sorted list of integers:");
System.out.println(numbers);
//Searching with sorted search
System.out.print(" (Sorted Search) Enter a number:");
x = in.nextInt();
if (numbers.sortedSearch(x))
System.out.println("Found!");
else
System.out.println("Not found!");
//Searching with binary search
System.out.print(" (Binary Search) Enter a number:");
x = in.nextInt();
if (numbers.binarySearch(x))
System.out.println("Found!");
else
System.out.println("Not found!");
}
}
Explanation / Answer
public class Lab5A
{
public static void main(String[] args)
{
Lab5A myAppl = new Lab5A();
}
public Lab5A()
{
Scanner in = new Scanner(System.in);
//List creation and display
int n = 4000000;
ArrayList numbers = new ArrayList(n);
for (int i = 0; i < n; i++)
numbers.add((int) (Math.random() * 1000));
//Searching with sequential search
System.out.print(" (Sequential Search) Enter a number:");
int x = 1000; //in.nextInt();
long startTime= System.currentTimeMillis();
if (numbers.sequentialSearch(x))
System.out.println("Found!");
else
System.out.println("Not found!");
long endTime = System.currentTimeMillis();
System.out.println("Time Taken = " + (endTime - startTime));
//Sorting the list
numbers.quicksort();
//Searching with sorted search
System.out.print(" (Sorted Search) Enter a number:");
x = 1000;
startTime= System.currentTimeMillis();
if (numbers.sortedSearch(x))
System.out.println("Found!");
else
System.out.println("Not found!");
endTime = System.currentTimeMillis();
System.out.println("Time Taken = " + (endTime - startTime));
//Searching with binary search
startTime= System.currentTimeMillis();
System.out.print(" (Binary Search) Enter a number:");
x = 1000;
startTime= System.currentTimeMillis();
if (numbers.binarySearch(x))
System.out.println("Found!");
else
System.out.println("Not found!");
endTime = System.currentTimeMillis();
System.out.println("Time Taken = " + (endTime - startTime));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.