Question

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.

Answer 1

//java program for searching and sorting

import java.util.*;

class SearchingSorting
{
   int array[];
   int size;
   SearchingSorting()
   {
       array=null;
       size=0;
   }
  
   SearchingSorting(int a[])
   {
       size=a.length;
       array=new int[size]; //getting length of a[] passed
       for(int i=0;i<size;i++) //storing each parametered a[] to array[]
       array[i]=a[i];
   }
  
   void showArray() //method for showing unsorted array
   {
      
       for(int i=0;i<size;i++) //repeat upto size and display each element
       System.out.print(" "+array[i]);
   System.out.println();//new line break
   }
  
   int linearSearch() //method to unsorted array search
   {
       int item;
       Scanner s=new Scanner(System.in);
       System.out.println("Enter element to search : ");
       item=s.nextInt();
       for(int i=0;i<size;i++)
       if(array[i]==item)   //if found return relative index value
       return i;
   return -1; //if not found return -1
   }
      
   int binarySearch()
   {
       int item,beg,end,mid;
       Scanner s=new Scanner(System.in); //scanner object for reading values
       System.out.println("Enter element to search : ");
       item=s.nextInt(); //input item to search
       beg=0;end=size-1;
       mid=(beg+end)/2; //calculation of mid location
       while(beg<=end && array[mid]!=item) //repeat loop until element found
       {
           if(item>array[mid]) //if right partition
           beg=mid+1;
           else if(item<array[mid])//if left partition
           end=mid-1;
       mid=(beg+end)/2; //new mid calculation
       }
       if(array[mid]==item)
       return mid;
       else
       return -1;
   }
  
   void sort()
   {
       quickSort(array,0,size-1); //calling recursive function
   }
   private void quickSort(int arr[],int low,int high)
   {
       int i=low,j=high; //getting i, j
       int temp; // for swapping
       int pivot=arr[(low+high)/2];//getting pivot element
       //partioning #1
       while(i<=j)
       {
           while(arr[i]<pivot) //searching for greater element than pivot
           i++;
           while(arr[j]>pivot)//searching for smaller element than pivot
           j--;
           if(i<=j)
           {
           //swapping process
               temp=arr[i];
               arr[i]=arr[j];
               arr[j]=temp;
               i++;
               j--;
           }
       }
       if(low<j) //recursive call1
       quickSort(arr,low,j);
       if(i<high)//recursive call2
       quickSort(arr,i,high);
}

public static void main(String args[])
{
   int scount=0;
   int a[]={23, 17, 5, 90, 12, 44, 38, 84, 77, 3, 66, 55, 1, 19, 37, 88, 8, 97, 25, 50, 75, 61, 49}; //array initialize
   SearchingSorting s1=new SearchingSorting(a);
   System.out.println("Unsorted array (output #1) : ");
   s1.showArray();
   System.out.println("Linear Searching item position (output #2): "+s1.linearSearch());
   for(int i=1;i<=5;i++)
   scount+=s1.linearSearch(); //counting 05 elements linear searches
   System.out.println("Linear Searching Total no.of searches (output #3): "+scount);
   scount=0; //reset search count
   s1.sort();
   System.out.println("Sorted array (output #4): ");
   s1.showArray();
   System.out.println("Binary Searching item position (output #5): "+s1.binarySearch());
   for(int i=1;i<=5;i++)
   scount+=s1.binarySearch(); //counting 05 elements binary searches
   System.out.println("Binary Searching Total no.of searches (output #6): "+scount);
}
}

//output