java not c++ Your assignment is to write a program that creates a single dimensi
ID: 3762318 • Letter: J
Question
java not c++
Your assignment is to write a program that creates a single dimensioned array of integers, fills it with random numbers, then sorts the array, and does searches in the array.
Your program must first request the user to input an array size. This size may be any integer from 1 to 50,000 (make certain to verify that the input is a number and that the number is within this range and if not, ask for a number again and again until you get a number if the correct range). Next your program will create an array of this size and fill the array with random numbers from 1 and the array size. Next it will copy this array into another array that your program crates that is the same size. The program then invokes a method that you will create that sorts the input array (but not the copied one). This method is to have a single input, the array. Next if the size of the array is 16 or less, the program will display the contents of both the sorted and unsorted arrays so that the sort routine can be verified.
Next the program will solicit a search number between 1 and array size from the user (make certain to verify that the input value is a number and that the number is within this range and if not, ask for a number again and again until you get an integer number if the correct range).
Next your program will invoke a method you will write that uses a linear search to find the input search number in the sorted array. The method will return the position within the array (0 to array size less 1) if it finds the number. Otherwise it will return a minus one (-1). The program will then display a message giving the location of the find or state that the number was not in the array. Immediately before and after the invoke of the search, your program is to invoke System.nanoTime() and save these values in variables of type long. It then subtracts the before time from the after time and displays the difference with a message stating how long the linear search took in nanoseconds. Note there are some problems with this timer, but use it anyway and see how it works.
Next your program will invoke a method you will write that uses a binary search to find the search number in the sorted array. The method will return the position within the array (0 to array size less 1) if it finds the number, otherwise it will return a minus one (-1). Immediately before and after the invoke of the search, your program is to invoke System.nanoTime () and save these values. It then subtracts in before time from the after time and displays the difference with a message stating how long the binary search took in nanoseconds.
Also make a flow chart of your program and hand it in. Make certain to show all loops, ifs, and processing symbols.
Note that the two search routines might return different locations even if they are both working correctly because a number could be duplicated in the array. Also it may not make a find because using random will not necessarily give you all of the numbers between 1 and the array size and may duplicate some.
Sort and search routines are in you book and also available on the Internet – feel free to use them, but give credit in your comments if it comes from a copyrighted source.
Explanation / Answer
import java.util.Random;
import java.util.Scanner;
/**
* @author srinu
*
*/
public class AssignmentSearch {
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
int arraySize;
do {
System.out.print("Please enter array size from 1 to 50,000:");
arraySize = scanner.nextInt();
if (arraySize >= 1 && arraySize <= 50000) {
break;
}
} while (true);
int A[] = new int[arraySize];
A = setArrayRandom(arraySize);
//A[0]=98;
int B[] = new int[arraySize];
for (int i = 0; i < arraySize; i++) {
B[i] = A[i];
}
A = sortArray(A);
if (arraySize <= 16) {
System.out.println("Sorted Array :");
displayArray(A);
System.out.println(" UnSorted Array :");
displayArray(B);
}
int number;
do {
System.out.print(" Please enter array size from 1 to 50,000:");
number = scanner.nextInt();
if (number >= 1 && number <= 50000) {
break;
}
} while (true);
long startTime, stopTime;
System.out.println("1. Sequential Search :");
startTime = System.nanoTime();
int position = Seq_search(A, number);
if (position != -1) {
System.out.println(number + " found at " + position);
} else {
System.out.println(number + " number was not in the array");
}
stopTime = System.nanoTime();
System.out.println("Time Taken For Sequential Search in nano seconds :"
+ (stopTime - startTime));
System.out.println("2. Binary Search :");
startTime = System.nanoTime();
position = binarySearch(A, number);
if (position != -1) {
System.out.println(number + " found at " + position);
} else {
System.out.println(number + " number was not in the array");
}
stopTime = System.nanoTime();
System.out.println("Time Taken For Binary Search in nano seconds :"
+ (stopTime - startTime));
}
/**
* @param inputArr
* @param key
* @return
*/
public static int binarySearch(int[] inputArr, int key) {
int start = 0;
int end = inputArr.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (key == inputArr[mid]) {
return mid;
}
if (key < inputArr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
/**
* @param numbers
* @param key
* @return
*/
public static int Seq_search(int[] numbers, int key) {
for (int index = 0; index < numbers.length; index++) {
if (numbers[index] == key) {
return index; // We found it!!!
}
}
// If we get to the end of the loop, a value has not yet
// been returned. We did not find the key in this array.
return -1;
}
/**
* @param arraySize
* @return
*/
public static int[] setArrayRandom(int arraySize) {
int min = 1, max = arraySize;
Random rand = new Random();
int array[] = new int[arraySize];
for (int i = 0; i < arraySize; i++) {
int randomNum = rand.nextInt((max - min) + 1) + min;
array[i] = randomNum;
}
return array;
}
/**
* @param nos
* @param n
* @return
*/
private static int[] sortArray(int nos[]) {
for (int i = 1; i < nos.length; i++) {
int j = i;
int B = nos[i];
while ((j > 0) && (nos[j - 1] > B)) {
nos[j] = nos[j - 1];
j--;
}
nos[j] = B;
}
return nos;
}
/**
* @param arraySize
*/
public static void displayArray(int array[]) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
}
OUTPUT
Please enter array size from 1 to 50,000:15
Sorted Array :
2 3 5 5 6 7 13 13 13 14 14 14 15 15 15
UnSorted Array :
15 15 3 13 6 5 15 14 5 13 13 14 14 2 7
Please enter array size from 1 to 50,000:5
1. Sequential Search :
5 found at 2
Time Taken For Sequential Search in nano seconds :232199
2. Binary Search :
5 found at 3
Time Taken For Binary Search in nano seconds :95360
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.