Step 1: Select any four sorting algorithm and three searching algorithms Step 2:
ID: 3739652 • Letter: S
Question
Step 1: Select any four sorting algorithm and three searching algorithms
Step 2: Understand the logic of all the algorithms
Step 3: Create java program and use your sorting/searching source codes and integrate it into your main java project.
Step 4: Create a separate java class for each algorithm
Step 5: Create a random function that generates at least 100000 random integer numbers from 1 to 1 million(No need to print out or store the numbers)
Step 6: Insert start transaction and end transaction for each sorting and searching methods
Step 7: Calculate the time in milliseconds for each sorting and searching class
Step 8: Compare the performance of each algorithm I only want a single java class with the main method. Your java program with the main method should call different sorting and searching classes. You need to have a separate class file for each sorting and searching methods.
Note: for the searching algorithm. please, use bubble, linear, and binary, ONLY, for the the FOUR sorting.
Explanation / Answer
--------------------------BubbleSort.java--------------------------
// Java program for implementation of Bubble Sort
class BubbleSort
{
// function to sort array a using bubble sort
public void bubble_sort(int a[])
{
int i, j, x;
for( i = 0 ; i < a.length - 1 ; i++)
{
for( j = 0 ; j < a.length - i - 1 ; ++j)
{
if (a[ j + 1 ] < a[ j ])
{
// swap the j and j + 1 th element of a
x = a[j];
a[ j ] = a[ j + 1 ];
a[ j + 1 ] = x;
}
}
}
}
}
----------------------------------InsertionSort.java-------------------------------
import java.util.*;
public class InsertionSort
{
public void insertion_sort(int[] a)
{
int i, j, temp;
for (i = 1; i < a.length; i++)
{
// store the current element in temp
temp = a[i];
// set j to i - 1
j = i - 1;
// all elements greater than temp are
// shifted 1 position right
while (j >= 0 && a[j] > temp)
{
// shifted 1 position right
a[j+1] = a[j];
j--;
}
a[j + 1] = temp;
}
}
}
--------------------------------------SelectionSort.java--------------------------------
?
import java.util.*;
public class SelectionSort
{
// sort using selection sort
public void selection_sort(int[] a)
{
int i, j, min, x;
// traverse the array
for (i = 0; i < a.length - 1; i++)
{
// store the index of the smallest element
min = i;
// traverse the array from the element after i till the end
for (j = i + 1; j < a.length; j++)
{
// if the current element is smaller than the min element
if (a[j] < a[min])
min = j;
}
// Swap first element and min
x = a[min];
a[min] = a[i];
a[i] = x;
}
}
}
--------------------------------------------QuickSort.java-----------------------------------------
public class QuickSort
{
public void quick_sort(int[] arr,int p,int r)
{
if(p < r)
{
// get the partition
int q = partition(arr,p,r);
// sort left subarray
quick_sort(arr, p, q - 1);
// sort right subarray
quick_sort(arr, q + 1, r);
}
}
public int partition(int[] arr,int p,int r)
{
int i,j;
int pivot, temp;
i = p - 1;
pivot = arr[r];
for(j = p; j < r; j++)
{
if(arr[j] <= pivot)
{
i++;
// swap the elements
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
arr[r] = arr[i + 1];
arr[i + 1] = pivot;
return (i+1);
}
}
-------------------------------------LinearSearch.java--------------------------------------
public class LinearSearch
{
public boolean linearSearch(int[] arr , int key)
{
int i;
for( i = 0 ; i < arr.length ; i++ )
// if element is found
if( arr[i] == key )
return true;
// if element is not found
return true;
}
}
------------------------------------BinarySearch.java---------------------------------
public class BinarySearch
{
public boolean binarySearch(int[] arr , int p, int r, int key)
{
if( p < r )
{
int mid = ( p + r ) / 2;
// if element is found
if( arr[mid] == key )
return true;
// if element lies in right subarray
else if( arr[mid] < key )
return binarySearch(arr, mid + 1, r, key);
// if element lies in left subarray
else
return binarySearch(arr, p, mid - 1, key);
}
// if element is not found
else
return false;
}
}
----------------------------------------Test.java--------------------------------
import java.util.*;
public class Test
{
public static void main(String[] args)
{
int maxSize = 100000;
int i = 0, j = 0;
long x;
// initialize the array
int[] a = new int[maxSize];
int[] b = new int[maxSize];
int[] c = new int[maxSize];
int[] d = new int[maxSize];
// fill the array with random elements
for(j = 0; j < maxSize; j++)
{
int n = (int)( java.lang.Math.random()*(maxSize-1) );
a[j] = n;
b[j] = n;
c[j] = n;
d[j] = n;
}
// get the current time
long start = System.currentTimeMillis();
SelectionSort ob = new SelectionSort();
// sort using bubble sort
ob.selection_sort(a);
// get the current time
long end = System.currentTimeMillis();
long time_taken = end - start;
System.out.println("Time Taken for Selection Sort: " + time_taken);
// Insertion Sort
InsertionSort is = new InsertionSort();
// get the current time
start = System.currentTimeMillis();
// sort using quick sort
is.insertion_sort(b);
// get the current time
end = System.currentTimeMillis();
time_taken = end - start;
System.out.println("Time Taken for Insertion Sort: " + time_taken);
// Bubble Sort
BubbleSort bs = new BubbleSort();
// get the current time
start = System.currentTimeMillis();
// sort using bubble sort
bs.bubble_sort(c);
// get the current time
end = System.currentTimeMillis();
time_taken = end - start;
System.out.println("Time Taken for Bubble Sort : " + time_taken);
// QuickSort
QuickSort qs = new QuickSort();
// get the current time
start = System.currentTimeMillis();
// sort using quicksort
qs.quick_sort(d, 0, d.length - 1);
// get the current time
end = System.currentTimeMillis();
time_taken = end - start;
System.out.println("Time Taken for quick sort : " + time_taken);
// search algorithms
// create a Random object
Random rand = new Random();
// create a Random object
Scanner sc = new Scanner(System.in);
System.out.print("Enter n : ");
int n = sc.nextInt();
int[] arr = new int[n];
for( i = 0 ; i < n ; i++ )
arr[i] = rand.nextInt( 1000 - ( -1000 ) + 1 ) - 1000;
int key = 5000;
LinearSearch ls = new LinearSearch();
// get the current time
long start_linear = System.currentTimeMillis();
boolean flag1 = ls.linearSearch(arr, key);
// get the current time
long end_linear = System.currentTimeMillis();
long time_linear = end_linear - start_linear;
BinarySearch bs1 = new BinarySearch();
// get the current time
long start_binary = System.currentTimeMillis();
boolean flag2 = bs1.binarySearch(arr, 0, arr.length, key);
// get the current time
long end_binary = System.currentTimeMillis();
long time_binary = end_binary - start_binary;
System.out.println("Time Taken for Linear Search ; " + time_linear);
System.out.println("Time Taken for Binary Search ; " + time_binary);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.