Write a program which will do the following. Make sure you use methods in your p

Question

Write a program which will do the following. Make sure you use methods in your program.

1. Create an array of 50 random integers in the range of 1 to 100.

2. Sort the array in descending order using either the selection sort, insertion sort or bubble sort (you

choose). The sort algorithms given all sort in ascending order so you will have to modify the

algorithm you choose to sort in descending order.

3. Generate ten (10) random integers in the range of 1 to 100 and use binary search to see if the

integers generated are in the sorted array. The binary search algorithm in your text assumes

ascending order so you will need to modify the algorithm to search a list in descending order.

4. For each of the ten (10) integers generated indicate if it is found in the list or not. If it is found

indicate at which index it was located (first occurrence), if not found it returns -1 so, print that out.

Also, for each integer generated indicate how many comparisons it took to either find or not find it

in the list.

5. Output to a file:

1. The unsorted list

2. The sorted list

3. For each generated integer:

1. Found at index ___ in the sorted list or not found in the sorted list.

2. Number of comparisons to find the integer in the list or number of comparisons to

not find the integer in the list.

Explanation / Answer

import java.util.Random;

public class BinarySearchAndSort {
  
   public static void doSelectionSort(int[] arr){
int n = arr.length-1;
for (int i = n; i > 0; i--)
{
int index = i;
for (int j = i-1; j>=0; j--)
if (arr[j] < arr[index])
index = j;
  
int temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
}
}
  
   public static int binarySearch(int[] inputArr, int key) {
  
int start = 0;
int end = inputArr.length - 1;
int numComparison = 0;
while (start <= end) {
int mid = (start + end) / 2;
if (key == inputArr[mid]) {
   System.out.println("Number of Comparision: "+(numComparison+1));// 1 for last comparison
return mid;
}
if (key < inputArr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
numComparison++;
}
System.out.println("Number of Comparision: "+(numComparison));
return -1;
}

   public static void main(String[] args) {
       Random r= new Random();
       int arr[] = new int[50];
       for(int i=0;i<50;i++){
           arr[i] = r.nextInt(100)+1; // [1-100]
       }
       for(int i:arr){
           System.out.print(i+" ");
       }
       System.out.println();
       doSelectionSort(arr); // selection sort
       for(int i:arr){
           System.out.print(i+" ");
       }
      
       int searchNum[] = new int[10];
       for(int i=0; i<10; i++)
           searchNum[i] = r.nextInt(100)+1;
      
       for(int i=0; i<10; i++){
           System.out.println("-------------------------------------------");
           int index = binarySearch(arr, searchNum[i]);
           if(index != -1){
               System.out.println("Element "+searchNum[i]+" found at index "+index);
           }else{
               System.out.println("Element "+searchNum[i]+" not found ");
           }
       }
   }
  
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.