I am currently using eclipse to write in java.
A snapshot of the output would be greatly appreciated to verify that the program is indeed working. Thanks in advance for both your time and effort.
Here is the previous exercise code:
/////////////////////////////////////////////////////Main
/*******************************************
* Week 5 lab - exercise 1 and exercise 2: *
* ArrayList class with search algorithms *
********************************************/
import java.util.*;
/**
* Class to test sequential search, sorted search, and binary search
algorithms
* implemented in ArrayList.
*/
public class Main
{
public static void main(String[] args)
{
Main myAppl = new Main();
}
public Main()
{
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("\n(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("\nSorted list of integers:");
System.out.println(numbers);
//Searching with sorted search
System.out.print("\n(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("\n(Binary Search) Enter a number:");
x = in.nextInt();
if (numbers.binarySearch(x))
System.out.println("Found!");
else
System.out.println("Not found!");
}
}
////////////////////////////////////////ArrayList
/*******************************************
* Week 5 lab - exercise 1 and exercise 2: *
* ArrayList class with search algorithms *
********************************************/
/**
* Class implementing an array based list. Sequential search, sorted
search, and
* binary search algorithms are implemented also.
*/
public class ArrayList
{
/**
* Default constructor. Sets length to 0, initializing the list as
an empty
* list. Default size of array is 20.
*/
public ArrayList()
{
SIZE = 20;
list = new int[SIZE];
length = 0;
}
/**
* Determines whether the list is empty
*
* @return true if the list is empty, false otherwise
*/
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. List length is
increased by 1.
*
* @param x element to be added to 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. List
length is
* decreased by 1.
*
* @param pos location of the item to be removed
*/
public void removeAt(int pos)
{
for (int i = pos; i < length - 1; i++)
list[i] = list[i + 1];
length--;
}
//Implementation of methods in the lab exercise
/**
* Non default constructor. Sets length to 0, initializing the list
as an
* empty list. Size of array is passed as a parameter.
*
* @param size size of the array list
*/
public ArrayList(int size)
{
SIZE = size;
list = new int[SIZE];
length = 0;
}
/**
* Returns the number of items in the list (accessor method).
*
* @return the number of items in the list.
*/
public int getLength()
{
return length;
}
/**
* Returns the size of the list (accessor method).
*
* @return the size of the array
*/
public int getSize()
{
return SIZE;
}
/**
* Removes all of the items from the list. After this operation, the
length
* of the list is zero.
*/
public void clear()
{
length = 0;
}
/**
* Replaces the item in the list at the position specified by
location.
*
* @param location location of the element to be replaced
* @param item value that will replace the value at 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.
*
* @param location location where item will be added.
* @param item item to be added to the list.
*/
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 an item from the list. All occurrences of item in the
list will
* be removed.
*
* @param item element to be removed.
*/
public void remove(int item)
{
for (int i = 0; i < length; i++)
if (list[i] == item)
{
removeAt(i);
i--; //onsecutive values won't be all removed; that's
why i-- is here
}
}
/**
* Returns the element at location
*
* @param location position in the list of the item to be
returned
* @return 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.
*
* @return Copy of this ArrayList
*/
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.
*
* @param begin initial index of sublist to be quick-sorted.
* @param end last index of sublist to be quick-sorted.
*/
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;
}
/*The methods listed below are new additions to the ArrayList
class
* of Week 4*/
/**
* This method returns a string representation of the array list
elements.
* Classes with this method implemented can get its objects
displayed in a
* simple way using System.out.println. For example, if list is an
ArrayList
* object, it can be printed by using
*
* System.out.println(list);
*
* @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
(linear)
* search.
*
* @param x item to be found.
* @return true if x is found in the list, false otherwise.
*/
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. List
* must be sorted.
*
* @param x item to be found.
* @return true if x is found in the list, false otherwise.
*/
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. List
* must be sorted.
*
* @param x item to be found.
* @return true if x is found in the list, false otherwise.
*/
public boolean binarySearch(int x)
{
int first = 0, last = length - 1, 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;
}
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
}
========================================================
Main.java
========================================================
/**
* Class to test sequential search, sorted search, and binary search
algorithms
* implemented in ArrayList.
*/
public class Main {
public static void main(String[] args)
{
Main myAppl = new Main();
}
public Main() {
// List creation and
display
int n = 10000;
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);
long startTime;
long endTime;
long timeDiff;
long
seqTime,sortedTime,binaryTime;
System.out.println("Total number
of intergers are : "+n);
System.out.println("-----------------------------------------------------");
System.out.println("SerachElements
SeqSearch SortedSearch BinarySearch");
System.out.println("(size) (time in
ms) (time in ms) (time in ms)");
System.out.println("-----------------------------------------------------");
for(int
j=100;j<=1000;j+=100) {
startTime =
System.currentTimeMillis();
for (int
i = 0; i < j; i++) {
int x = (int) (Math.random() * 100);
numbers.sequentialSearch(x);
}
endTime =
System.currentTimeMillis();
timeDiff =
endTime - startTime;
seqTime =
timeDiff;
startTime =
System.currentTimeMillis();
for (int
i = 0; i < j; i++) {
if(j==100){
// Sorting the list
numbers.quicksort();
}
// Searching with sorted search
int x = (int) (Math.random() * 100);
numbers.sortedSearch(x);
}
endTime =
System.currentTimeMillis();
timeDiff =
endTime - startTime;
sortedTime =
timeDiff;
startTime =
System.currentTimeMillis();
for (int
i = 0; i < j; i++) {
// Searching with binary search
int x = (int) (Math.random() * 100);
numbers.binarySearch(x);
}
endTime =
System.currentTimeMillis();
timeDiff =
endTime - startTime;
binaryTime =
timeDiff;
System.out.println(j+"\t\t"+seqTime+"\t\t"+sortedTime+"\t\t"+binaryTime);
}
System.out.println("-----------------------------------------------------");
}
}
I am currently using eclipse to write in java. A snapshot of the output would be...
C++ Time the sequential search and the binary search methods several times each for randomly generated values, then record the results in a table. Do not time individual searches, but groups of them. For example, time 100 searches together or 1,000 searches together. Compare the running times of these two search methods that are obtained during the experiment. Regarding the efficiency of both search methods, what conclusion can be reached from this experiment? Both the table and your conclusions should...
JAVA- Trace the recursive quick sort and partition methods in Lab6.java for this list of numbers: 47 71 15 35 66 61 44 26 68 56 18 19 36 84 69 55 1. Find the value of pivot 2. Show the result after partitionIt() is called first time 3. Show the value of partition 4. Show the content of the array ///////////////////////////// Lab6.java class ArrayIns { private long[] theArray; // ref to array theArray private int nElems; // number of...
Java Programming Write a program to find the number of comparison using binarySearch and the sequentialSearch algorithms as follows: Suppose list is an array of 2500 elements. 1. Use a random number generator to fill list; 2. Use a sorting algorithm to sort list; 3. Search list for some items as follows: a) Use the binary search algorithm to search list (please work on SearchSortAlgorithms.java and modify the algorithm to count the number of comparisons) b) Use the sequential search...
Need help with this Java. I need help with the "to do" sections. Theres two parts to this and I added the photos with the entire question Lab14 Part 1: 1) change the XXX to a number in the list, and YYY to a number // not in the list 2.code a call to linearSearch with the item number (XXX) // that is in the list; store the return in the variable result 3. change both XXX numbers to the...
Language C++ (Please include a short description & Screenshot of output) Implement a Priority queue using a SORTED list. Use Quick sort after adding a new node. Example of quick sort below. Adopt to your program the code below. #include <iostream> void quickSort(int a[ ], int first, int last); int pivot(int a[], int first, int last); void swap(int& a, int& b); void swapNoTemp(int& a, int& b); void print(int array[], const int& N); using namespace std; int main() { int test[]...
//Generic interface that describes various searching and sorting //algorithms. Note that the type parameter is unbounded. However, //for these algorithms to work correctly, the data objects must //be compared using the method compareTo and equals. //In other words, the classes implementing the list objects //must implement the interface Comparable. The type parameter T //is unbounded because we would like to use these algorithms to //work on an array of objects as well as on objects of the classes //UnorderedArrayList and...
I currently have this but it doesn't work for the three item arrays public class Quicksort extends Partitioner { public static void quicksort(int[] values) { if (values == null || values.length < 2) { return; } quicksort(values, 0, values.length - 1); } private static void quicksort(int[] values, int start, int end) { System.out.println(values); System.out.println(start); System.out.println(end); if (values == null || Math.abs(start - end) == 1) { return; } if (end > start) { int pivotValueIndex = partition(values, start, end); quicksort(values,...
Copy the following java codes and compile //// HighArray.java //// HighArrayApp.java Study carefully the design and implementation HighArray class and note the attributes and its methods. Create findAll method which uses linear search algorithm to return all number of occurrences of specified element. /** * find an element from array and returns all number of occurrences of the specified element, returns 0 if the element does not exit. * * @param foundElement Element to be found */ int findAll(int...
import java.util.Arrays; public class lab { public static void main(String args[]) { int arr[] = {10, 7, 8, 9, 1, 5,6,7}; int arr2[] = {9, 8, 7, 6, 5, 4, 3, 2, 1}; int arr3[] = {1, 3, 5, 3, 2, 6, 20}; quicksort(arr,0,arr.length-1); quicksort(arr2,0,arr2.length-1); quicksort(arr3,0,arr3.length-1); System.out.println(Arrays.toString(arr)); System.out.println(Arrays.toString(arr2)); System.out.println(Arrays.toString(arr3)); } private static int partition(int[] items,int low, int high) { int i=0; int j=0;...
Need help with this Java project implementing an interpolation search, bolded the missing parts: /** A class that implements an interpolation search and a binary search of a sorted array of integers. @author Frank M. Carrano @author Timothy M. Henry @version 4.0 */ public class SearchComparer { private int[] a; private int interpolationSearchCounter; private int binarySearchCounter; private static final int CAPACITY = 50; public SearchComparer(int[] array, int n) {...