Write a program that Calls a method called insertionSort that accepts an integer
ID: 3681306 • Letter: W
Question
Write a program that Calls a method called insertionSort that accepts an integer array as a parameter and sorts the elements in the array using the insertion sort algorithm. Print the array before it is sorted and after it is sorted. Calls another method called binarySeareh that takes two parameters, an integer and an integer array. The call should perform binary search and should return the index of the integer in the array if found and should return -(insertionPoint+ 1) if the number is not found. Print out the index in the main method.Explanation / Answer
ArrayHelper.java
public class ArrayHelper {
/**
* private constructor: to prevent instantiating the class
*/
private ArrayHelper() {}
/**
* swap the elements at indices i and j of array v.
* Assuming i, j are both in the right range.
* @param v
* @param i
* @param j
*/
public static void swap(int[] v, int i, int j) {
int temp = v[i];
v[i] = v[j];
v[j] = temp;
}
/**
* find the minimum value in array v in the range from index k (inclusive)
* to the end and return its index
* @param v
* @param k the starting index
* @return the index of the minimum value
*/
public static int min(int[] v, int k) {
int least = k;
for(int i=k; i<v.length; ++i)
if(v[i] < v[least]) {
least = i;
}
return least;
}
/**
* selectionSort gradually sorts an array by finding the smallest element in
* the remaining unsorted portion of the array and putting it at the right spot.
*
* running time: n*n (n: the length of the array)
* @param v
*/
public static void selectionSort(int[] v) {
for(int i=0; i<v.length; ++i) {
// step 1: find the ith lowest value
int index = min(v, i);
// swap that value with the current value at index i
swap(v, i, index);
}
}
/**
* Searches the specified array of ints for the specified value using the
* binary search algorithm. The array <strong>must</strong> be sorted
* prior to making this call. If it
* is not sorted, the results are undefined. If the array contains
* multiple elements with the specified value, there is no guarantee which
* one will be found.
*
* @param v the array to be searched.
* @param key the value to be searched for.
* @return index of the search key, if it is contained in the list;
* otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.
*/
public static int binarySearch(int[] v, int key) {
// the search range is between low (inclusive) and high (exclusive)
int low = 0; int high = v.length;
while(low!=high) { // ?
int mid = (low + high)/2;
if(v[mid]==key)
return mid;
else if(v[mid]>key) {
high=mid;
} else { // v[mid] < key
low = mid + 1;
}
}
return -(low+1);
}
/**
* search for element key within the range between low (inclusive) and
* high (exclusive) of v.
* @param v
* @param key
* @param low
* @param high
* @return the index
*/
private static int binarySearch(int[] v, int key, int low, int high) {
if(low==high)
return -(low+1);
int mid = (low+high)/2;
if(v[mid]==key) // found
return mid;
else if(v[mid]<key) // key is in the right half
return binarySearch(v, key, mid+1, high);
else // v[mid]>key, which means key is in the left half
return binarySearch(v, key, low, mid);
}
public static void insertionSort(int[] v) {
for(int i=1; i<v.length; ++i) {
int key = v[i];
int insertionPoint = binarySearch(v,key,0,i);
if(insertionPoint<0)
insertionPoint = -insertionPoint - 1;
if(insertionPoint<i){
// slide the elements from insertionPoint to i-1 down by one spot
System.arraycopy(v,insertionPoint,v,insertionPoint+1,
i-insertionPoint);
v[insertionPoint]=key;
}
}
}
}
ArrayTest.java
import java.util.Arrays;
public class ArrayTest {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] v = {5,12,15,-1, 10, 7,5};
// ArrayHelper.selectionSort(v);
ArrayHelper.insertionSort(v);
System.out.println(Arrays.toString(v));
// the following code sorts a string
String s = "Thomas";
char[] a = s.toCharArray();
Arrays.sort(a);
String sorted = new String(a);
System.out.println(a);
}
}
sample output
[-1, 5, 5, 7, 10, 12, 15]
Tahmos
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.