Time the sequential search and the binary search methods several times each for
ID: 3553555 • Letter: T
Question
Time the sequential search and the binary search methods several times each for randomly generated values, and record the results in a table. 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 be included in a separate Word document.
/*******************************************
* Week 5 lab - exercise 1 and exercise 2: *
* ArrayList class with search algorithms *
********************************************/
public class ArrayList
{
public ArrayList()
{
SIZE = 20;
list = new int[SIZE];
length = 0;
}
public boolean isEmpty()
{
return length == 0;
}
public void display()
{
for (int i = 0; i < length; i++)
System.out.print(list[i] + " ");
System.out.println();
}
public void add(int x)
{
if (length == SIZE)
System.out.println("Insertion Error: list is full");
else
{
list[length] = x;
length++;
}
}
public void removeAt(int pos)
{
for (int i = pos; i < length - 1; i++)
list[i] = list[i + 1];
length--;
}
public ArrayList(int size)
{
SIZE = size;
list = new int[SIZE];
length = 0;
}
public int getLength()
{
return length;
}
public int getSize()
{
return SIZE;
}
public void clear()
{
length = 0;
}
public void replace(int location, int item)
{
if (location < 0 || location >= length)
System.out.println("Error: invalid location");
else
list[location] = item;
}
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++;
}
}
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
}
}
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;
}
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;
}
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;
}
}
public void quicksort()
{
quicksort(0, length - 1);
}
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);
}
private int findPivotLocation(int b, int e)
{
return (b + e) / 2;
}
public String toString()
{
String s = "";
for (int i = 0; i < length; i++)
s += list[i] + " ";
return s;
}
public boolean sequentialSearch(int x)
{
for (int i = 0; i < length; i++)
if (list[i] == x)
return true;
return false;
}
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
}
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
}
/*******************************************
* 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(" (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
Make the following changes to your main method: System.nanoTime() method calculates the running time before you call the method and after and then subtracting the difference for the running time in nanoseconds, if you want in milliseconds simply divide Before=Before/1000000 and so on...
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(" (Sequential Search) Enter a number:");
int x = in.nextInt();
Long before=System.nanoTime();
if (numbers.sequentialSearch(x))
System.out.println("Found!");
else
System.out.println("Not found!");
Long after=System.nanoTime();
System.out.println("Running time takes : "+(after-before)+ "ns");
//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();
Long before2=System.nanoTime();
if (numbers.binarySearch(x))
System.out.println("Found!");
else
System.out.println("Not found!");
Long after2=System.nanoTime();
System.out.println("Running time takes : "+(after2-before2)+ "ns");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.