Problem 1: Show the comparison of runtime of linear search and binary search usi
ID: 3797773 • Letter: P
Question
Problem 1: Show the comparison of runtime of linear search and binary search using line chart and table. Execute both algorithms 6 times on same data(use random integer generators), where input data size are: 50000, 100000, 150000, 200000, 250000, and 300000. Please report worst case runtimes so that the search item is not found in the input data.
Problem 2: Show the comparison of runtime of bubble sort and merge sort using line chart and table. Execute both algorithms 6 times on same data(use random integer generators), where data size are: 50000, 100000, 150000, 200000, 250000, and 300000. In each execution, sort the data in ascending order.
Explanation / Answer
Search & sort comparison for differnt sort & search algorithms.
Problem1: Java Code:
import java.util.Random;
public class SearchComparison {
public static void main(String[] args) {
//Compare linear & binary search for
//random data 6 times & print its execution time
System.out.println("--------------------------------");
//50000
searchComparison(50000);
System.out.println("--------------------------------");
//100000
searchComparison(100000);
System.out.println("--------------------------------");
//150000
searchComparison(150000);
System.out.println("--------------------------------");
//200000
searchComparison(200000);
System.out.println("--------------------------------");
//250000
searchComparison(250000);
System.out.println("--------------------------------");
//and 300000
searchComparison(300000);
System.out.println("--------------------------------");
}
/**
* searchComparison
* @param size
*/
public static void searchComparison(int size){
System.out.println("Input size:"+size);
//Generate random numbers list for given size
Random randomGenerator = new Random();
int list[]=new int[size];
for (int index = 0; index < size; ++index){
list[index]=randomGenerator.nextInt(size);
}
//For worst case key must be last number list[size-1]
long startTime=System.nanoTime();
linearSearch(list, list[size-1]);
long endTime=System.nanoTime();
long totalTime=(endTime-startTime); //time in nanoseconds
System.out.println("Linear search: input size="+size+" - time="+totalTime);
startTime=System.nanoTime();
binarySearch(list, list[size-1]);
endTime=System.nanoTime();
totalTime=(endTime-startTime); //time in milliseconds
System.out.println("Binary search: input size="+size+" - time="+totalTime);
}
/**
* Linearly search key in list[]. If key is present then return the index,
* otherwise return -1
*
* @param list
* @param key
* @return
*/
public static int linearSearch(int list[], int key) {
for (int index = 0; index < list.length; index++) {
if (list[index] == key)
return index;
}
return -1;
}
/**
* BinarySearch search key in list[]. If key is present then return the
* index, otherwise return -1
*
* @param list
* @param key
* @return
*/
public static int binarySearch(int list[], int key) {
int lo = 0;
int hi = list.length - 1;
while (lo <= hi) {
// Key is in list[lo..hi] or not present.
int mid = lo + (hi - lo) / 2;
if (key < list[mid])
hi = mid - 1;
else if (key > list[mid])
lo = mid + 1;
else
return mid;
}
return -1;
}
}
Steps to compile & run the program:
javac SearchComparison.java
java SearchComparison
Output:
--------------------------------
Input size:50000
Linear search: input size=50000 - time=2124844
Binary search: input size=50000 - time=16627
--------------------------------
Input size:100000
Linear search: input size=100000 - time=340572
Binary search: input size=100000 - time=18489
--------------------------------
Input size:150000
Linear search: input size=150000 - time=3344970
Binary search: input size=150000 - time=4584
--------------------------------
Input size:200000
Linear search: input size=200000 - time=668294
Binary search: input size=200000 - time=4557
--------------------------------
Input size:250000
Linear search: input size=250000 - time=77522
Binary search: input size=250000 - time=19226
--------------------------------
Input size:300000
Linear search: input size=300000 - time=164177
Binary search: input size=300000 - time=3978
--------------------------------
Problem 2: Java Code-
public class SortComparison {
public static void main(String[] args) {
// Compare linear & binary search for
// random data 6 times & print its execution time
System.out.println("--------------------------------");
// 50000
sortComparison(50000);
System.out.println("--------------------------------");
// 100000
sortComparison(100000);
System.out.println("--------------------------------");
// 150000
sortComparison(150000);
System.out.println("--------------------------------");
// 200000
sortComparison(200000);
System.out.println("--------------------------------");
// 250000
sortComparison(250000);
System.out.println("--------------------------------");
// and 300000
sortComparison(300000);
System.out.println("--------------------------------");
}
public static void sortComparison(int size) {
System.out.println("Input size:" + size);
// Generate random numbers list for given size
Random randomGenerator = new Random();
int list[] = new int[size];
for (int index = 0; index < size; ++index) {
list[index] = randomGenerator.nextInt(size);
}
long startTime = System.nanoTime();
bubbleSort(list);
long endTime = System.nanoTime();
long totalTime = (endTime - startTime); // time in nanoseconds
System.out.println("Bubble sort: input size=" + size + " - time=" + totalTime);
startTime = System.nanoTime();
mergesort(list);
endTime = System.nanoTime();
totalTime = (endTime - startTime); // time in milliseconds
System.out.println("Merge sort: input size=" + size + " - time=" + totalTime);
}
/**
* Method use bubble sort algorithm to sort list ascending order
*
* @param list
*/
public static void bubbleSort(int list[]) {
int temp = 0;
for (int index1 = 0; index1 < (list.length - 1); index1++) {
for (int index2 = 0; index2 < list.length - index1 - 1; index2++) {
if (list[index2] > list[index2 + 1]) {
temp = list[index2];
list[index2] = list[index2 + 1];
list[index2 + 1] = temp;
}
}
}
}
/**
* Method use merge sort algorithm to sort list ascending order
*
* @param list
* @return
*/
public static int[] mergesort(int[] list) {
int size = list.length;
if (size <= 1)
return list;
int[] temp1 = new int[size / 2];
int[] temp2 = new int[size - size / 2];
for (int index = 0; index < temp1.length; index++)
temp1[index] = list[index];
for (int index = 0; index < temp2.length; index++)
temp2[index] = list[index + size / 2];
return merge(mergesort(temp1), mergesort(temp2));
}
private static int[] merge(int[] temp1, int[] temp2) {
int[] temp3 = new int[temp1.length + temp2.length];
int index1 = 0, index2 = 0;
for (int index3 = 0; index3 < temp3.length; index3++) {
if (index1 >= temp1.length)
temp3[index3] = temp2[index2++];
else if (index2 >= temp2.length)
temp3[index3] = temp1[index1++];
else if (temp1[index1] <= temp2[index2])
temp3[index3] = temp1[index1++];
else
temp3[index3] = temp2[index2++];
}
return temp3;
}
}
Steps to compile & run the program:
javac SortComparison.java
java SortComparison
Output:
--------------------------------
Input size:50000
Bubble sort: input size=50000 - time=6442721760
Merge sort: input size=50000 - time=33285535
--------------------------------
Input size:100000
Bubble sort: input size=100000 - time=25841668982
Merge sort: input size=100000 - time=24046898
--------------------------------
Input size:150000
Bubble sort: input size=150000 - time=58446233927
Merge sort: input size=150000 - time=29973618
--------------------------------
Input size:200000
Bubble sort: input size=200000 - time=104861524269
Merge sort: input size=200000 - time=39586920
--------------------------------
Input size:250000
Bubble sort: input size=250000 - time=160468980476
Merge sort: input size=250000 - time=45671299
--------------------------------
Input size:300000
Bubble sort: input size=300000 - time=229789831510
Merge sort: input size=300000 - time=54097226
--------------------------------
Please draw line chart & table using above output data of search & sort comparison for differnt sort & search algorithms. Let me know in case any query in comment section.