Homework SourseUsing Arrays with Sorting and Searching Algorithms 1 This pr
Using Arrays with Sorting and Searching Algorithms
1) This program has six required outputs and involves searching and sorting an array of integers. Write a java application that initializes an array with the following numbers, in this order: 23, 17, 5, 90, 12, 44, 38, 84, 77, 3, 66, 55, 1, 19, 37, 88, 8, 97, 25, 50, 75, 61, and 49. Then display the unsorted values. This is required output #1 of 6 for this program.
2) Using a sequential search of the unsorted array, determine and report the relative (i.e. 0,1, 2, 3, 4, etc.) positions of the following numbers in the array (or -1 if not found), and the number of searches required to locate the numbers: 25, 30, 50, 75, and 92. This is required output #2 of 6.
3) Then display the total number of searches for all five numbers. This is required output #3 of 6.
4) Sort the numbers using a recursive quicksort and then display the sorted array. This is required output #4 of 6.
5) Using a binary search of the sorted array, determine and report the 1-relative positions of the following numbers in the array (or -1 if not found), and 2-the number of searches required to locate the numbers: 25, 30, 50, 75, and 92. This is required output #5 of 6.
6) Finally, display the total number of searches for all five numbers. This is required output #6 of 6.
(There are six required sets of output as numbered in the above paragraphs.)
Create an object-oriented solution for this assignment. Create a class called SArray (Search Array) that accepts the initial array through the constructor. The class should have a recursive quick sort sorting method that will sort the array. The class should have two methods for searching. One that does a sequential search that accepts as input the integer value that is to be searched for and returns the index in array where the search value is if found, and -1 if not found. The other search method should be a binary search of a sorted array that accepts as input the integer value that is to be searched for and returns the index in the array where the search value is if found, and -1 if not found. Create a toString method to display the contents of the array. The driver/main class could not only pass in the initial array values but call various methods to perform the searches, sorting, and array contents display thus enabling you to display the information in the six items above.
Include additional comments as necessary and maintain consistent indentation
Make sure you upload your java source code and a screen snapshot of all of your program\'s outputs to blackboard
Solution
import java.util.*;
//Class SArray definition
class SArray
{
//Array declaration
int arr[];
//Parameterized Constructor to assign array value
SArray(int a[])
{
arr = a;
}
//Display array
void toString(int a[])
{
for(int x = 0; x < arr.length; x++)
System.out.print(arr[x] + \" \");
}
//Sequential Search
int sequentialSearch(int a[], int s)
{
//Initially position is set to -1
int pos = -1;
//Loops till end of the array
for(int x = 0; x < arr.length; x++)
{
//If search item found
if(a[x] == s)
{
//Set the position and come out of the loop
pos = x;
break;
}
}
return pos;
}
//Recursive Quick Sort
public static void recursiveQuickSort(int[] arr, int startPo, int endPo)
{
int idP = partition(arr, startPo, endPo);
// Recursively call Quick Sort with Left part of the partitioned array
if (startPo < idP - 1)
{
recursiveQuickSort(arr, startPo, idP - 1);
}
// Recursively call Quick Sort with Right part of the partitioned array
if (endPo > idP)
{
recursiveQuickSort(arr, idP, endPo);
}
}
//Makes partition based on the Pivot value
public static int partition(int[] a, int left, int right)
{
int pivot = a[left]; // taking first element as pivot
while (left <= right)
{
//Searching number which is greater than pivot, bottom up
while (a[left] < pivot)
{
left++;
}
//Searching number which is less than pivot, top down
while (a[right] > pivot)
{
right--;
}
// Swap the values
if (left <= right)
{
int t = a[left];
a[left] = a[right];
a[right] = t;
//Increment left index
left++;
//Decrement right index
right--;
}
}
return left;
}
//Binary Search
int binarySearch(int arr[], int search, int counter[])
{
//Initialization the position to -1
int pos = -1;
//Initialization of first to zero
int first = 0;
//Initialization of last to length of the array - 1
int last = arr.length - 1;
//Calculates the middle value
int middle = (first + last) / 2;
//Loops till first is less than or equal to last
while( first <= last )
{
//Counter is increased to count number of comparisions
counter[0]++;
//If middle value of the array is less than the search element
if ( arr[middle] < search )
//Reset the first position to middle plus 1
first = middle + 1;
//If middle position of the array is equal to the search element
else if ( arr[middle] == search )
{
//Set the position to middle and come out of the loop
pos = middle;
break;
}
//If middle value of the array is greater than the search element
else
//Reset the last position to middle minus 1
last = middle - 1;
//Calculate again the middle position
middle = (first + last) / 2;
}
if (first > last)
return -1;
else
return pos;
}
}
//Driver class
class SArrayDemo
{
public static void main(String ss[])
{
int arr [] = {23, 17, 5, 90, 12, 44, 38, 84, 77, 3, 66, 55, 1, 19, 37, 88, 8, 97, 25, 50, 75, 61, 49};
SArray sa = new SArray(arr);
Scanner sc = new Scanner(System.in);
int x, y, tot;
//To display unsorted list
System.out.println(\"Unsorted Array \ \");
sa.toString(arr);
//Sequential search
tot = 0;
for(y = 0; y < 5; y++)
{
//Accept a number to search
System.out.print(\"\ Enter a number to search: \");
int no = sc.nextInt();
//Calls the Sequential Search method
x = sa.sequentialSearch(arr, no);
//Checks if the return value of the method is not -1 indicates item found
if(x != -1)
{
System.out.println(\"\ Searched Item \" + no + \" Found at Location: \" + x);
System.out.println(\"Number of searches required to locate the number\" + no + \" : \" + (x + 1));
//Calculates total number of search
tot += (x + 1);
}
//Checks if the return value of the method is -1 indicates item not found
else
{
System.out.println(\"\ Searched Item \" + no + \" Not Found: \");
System.out.println(\"Number of searches required to locate the number \" + no + \" : \" + arr.length);
//Calculates total number of search
tot += arr.length;
}
}//End of for loop
System.out.println(\"Total Number of Search Required: \" + tot);
//Quick Sort
//Call Quick Sort method
sa.recursiveQuickSort(arr, 0, arr.length - 1);
System.out.println(\"\ After Quick Sorting \ \");
sa.toString(arr);
//Binary Search
int count[] = new int[1];
//Reset the total counter for binary search
tot = 0;
for(y = 0; y < 5; y++)
{
count[0] = 0;
//Accept a number to search
System.out.print(\"\ Enter a number to search: \");
int no = sc.nextInt();
//Calls the Binary Search method
x = sa.binarySearch(arr, no, count);
//Checks if the return value of the method is not -1 indicates item found
if(x != -1)
{
System.out.println(\"\ Searched Item \" + no + \" Found at Location: \" + x);
System.out.println(\"Number of searches required to locate the number\" + no + \" : \" + count[0]);
//Calculates total number of search
tot += count[0];
}
//Checks if the return value of the method is -1 indicates item not found
else
{
System.out.println(\"\ Searched Item \" + no + \" Not Found: \");
System.out.println(\"Number of searches required to locate the number \" + no + \" : \" + count[0]);
//Calculates total number of search
tot += count[0];
}
}//End of for loop
System.out.println(\"Total Number of Search Required: \" + tot);
}
}
Output:
Unsorted Array
23 17 5 90 12 44 38 84 77 3 66 55 1 19 37 88 8 97 25 50 75 61 49
Enter a number to search: 25
Searched Item 25 Found at Location: 18
Number of searches required to locate the number25 : 19
Enter a number to search: 30
Searched Item 30 Not Found:
Number of searches required to locate the number 30 : 23
Enter a number to search: 50
Searched Item 50 Found at Location: 19
Number of searches required to locate the number50 : 20
Enter a number to search: 75
Searched Item 75 Found at Location: 20
Number of searches required to locate the number75 : 21
Enter a number to search: 92
Searched Item 92 Not Found:
Number of searches required to locate the number 92 : 23
Total Number of Search Required: 106
After Quick Sorting
1 3 5 8 12 17 19 23 25 37 38 44 49 50 55 61 66 75 77 84 88 90 97
Enter a number to search: 25
Searched Item 25 Found at Location: 8
Number of searches required to locate the number25 : 3
Enter a number to search: 30
Searched Item 30 Not Found:
Number of searches required to locate the number 30 : 4
Enter a number to search: 50
Searched Item 50 Found at Location: 13
Number of searches required to locate the number50 : 5
Enter a number to search: 75
Searched Item 75 Found at Location: 17
Number of searches required to locate the number75 : 2
Enter a number to search: 92
Searched Item 92 Not Found:
Number of searches required to locate the number 92 : 5
Total Number of Search Required: 19
