Please help. I need to sort the array I have created below according to the foll
ID: 3633655 • Letter: P
Question
Please help. I need to sort the array I have created below according to the following criteria:Using either of the sorting algorithms presented in class (selectionsort, insertionsort), sort your array, then implement the following search algorithm to look for a value requested by the user:
Look at the middle value of the array; if the value is found, you’re done. Otherwise, the value is either greater or less than this value If the search didn’t end in the step above, search the half of the array in which the value must be found (if the value is less than the middle value, search the half from the beginning up to midpoint-1; if the value is greater than the middle value, search from midpoint+1 up to length – 1) using the same method – that is, examine the middle value.
Continue the process of dividing the search area in half and examining the midpoint until either the value is found, or you are down to a search area of length 1 which does not contain the value.
As with the original search method, your program should report whether or not the value was found, and how many values you had to examine to determine the outcome.
import java.util.*;
public class Meep
{public static void main(String [] args)
{Random r=new Random();
int []a=new int[1000];
Scanner in=new Scanner(System.in);
int i,n;
for(i=0;i<1000;i++)
a[i]=r.nextInt(4999)+1;
System.out.print("Enter a number between 1 and 5000: ");
n=in.nextInt();
for(i=0;i<1000;i++)
if(n==a[i])
{System.out.println(n+" was found after searching "+(i+1)+" numbers");
System.exit(0);
}
System.out.println(n+" was not found in the array");
}
}
Explanation / Answer
Hi, here's a version of the code implementing selection Sort, also, the search you're describing sounds like a binary search (you can read up on it on wikipedia). The code pretty much follows your requirments, I hope it helps, please remember to rate !
import java.util.Random;
import java.util.Scanner;
public class Meep {
public static int searchCounter = 0;
public static void main(String[] args) {
Random r = new Random();
int[] a = new int[1000];
Scanner in = new Scanner(System.in);
int i, n;
for (i = 0; i < 1000; i++) {
a[i] = r.nextInt(4999) + 1;
}
// Sort your array
selectionSort(a);
// Search in your array
// reset the searchCounter to 0 before every new search
searchCounter = 0;
// get the item to search for from the user
System.out.print("Enter a number between 1 and 5000: ");
n = in.nextInt();
int result = search(a, n);
// search method returns -1 if not found
if(result == -1)
{
System.out.println(n + " was not found in the array");
}
// otherwise print out the result and the search Counter
else
{
System.out.println(n + " was found at position " + result +
" after searching " + searchCounter + " numbers");
System.exit(0);
}
}
public static void selectionSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j]) {
//... Exchange elements
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
// this is the search algorithm
public static int search(int[] array, int item) {
int low = 0;
int high = array.length - 1;
int mid;
while (low <= high) {
searchCounter++;
mid = (low + high) / 2;
if(array[mid] == item)
return mid;
if (array[mid] < item)
low = mid + 1;
if (array[mid] > item)
high = mid - 1;
}
return -1;
}
}