[1] Suppose that we have an array called list initialized as follows: (3 pts) in
ID: 3681692 • Letter: #
Question
[1] Suppose that we have an array called list initialized as follows: (3 pts)
int[] list = {-2, 8, 13, 22, 25, 25, 38, 42, 51, 103};
This would construct the following array:
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| -2 | 8 | 13 | 22 | 25 | 25 | 38 | 42 | 51 | 103 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
The following explains two types of binarySearch method in the Arrays class.
public static int binarySearch(int[] a, int target) {
return binarySearch(a, target, 0, a.length - 1);
}
public static int binarySearch(int[] a, int target,
int min, int max) {
if (min > max) {
return -1; // target not found
} else {
int mid = (min + max) / 2;
if (a[mid] < target) { // too small; go right
return binarySearch(a, target, mid + 1, max);
} else if (a[mid] > target) { // too large; go left
return binarySearch(a, target, min, mid - 1);
} else {
return mid; // target found; a[mid] == target
}
}
}
Please write complete BinarySearch class program with the above methods and the method call as follows and give the answer for the following questions.
System.out.println(binarySearch(list, 103, 0, 9));
System.out.println(binarySearch(list, 30, 2, 8));
[1.1] What values would min, max and mid take on for the following call in recursive fashion:
binarySearch(list, 103, 0, 9);
and what value would be returned?
[1.2] What values would min, max and mid take on for the following call in recursive fashion:
binarySearch(list, 30, 2, 8);
and what value would be returned?
O Sorting
[2] Consider the following array of int values. Please write TestSort class which includes the following selectionSort() program and try to call both methods on the following array. (6 pts.)
[7, 1, 6, 12, -3, 8, 4, 21, 2, 30, -1, 9]
[2.1] Explain the contents of the array after 4 passes of the outermost loop of selectionSort(). Please refer to the following selectionSort() method. (2 pts.)
public static void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
// find index of smallest remaining value
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
// swap smallest value its proper place, a[i]
swap(a, i, min);
}
}
// Swaps a[i] with a[j].
public static void swap(int[] a, int i, int j) {
if (i != j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
[2.2] Please write insertionSort() and bubbleSort()additionally and show how it works step by step with proper input by including proper output statements. (4 pts.)
Explanation / Answer
1).
public class BinarySearch {
public static int binarySearch(int[] a, int target) {
return binarySearch(a, target, 0, a.length - 1);
}
public static int binarySearch(int[] a, int target, int min, int max) {
if (min > max) {
System.out.println("Min: "+min+", Max: "+max);
return -1; // target not found
} else {
int mid = (min + max) / 2;
System.out.println("Min: "+min+", Mid: "+mid+", Max: "+max);
if (a[mid] < target) { // too small; go right
return binarySearch(a, target, mid + 1, max);
} else if (a[mid] > target) { // too large; go left
return binarySearch(a, target, min, mid - 1);
} else {
return mid; // target found; a[mid] == target
}
}
}
public static void main(String[] args) {
int[] list = {-2, 8, 13, 22, 25, 25, 38, 42, 51, 103};
System.out.println("Returned Value: "+binarySearch(list, 103, 0, 9));
System.out.println();
System.out.println("Returned Value: "+binarySearch(list, 30, 2, 8));
}
}
1.1):
Min: 0, Mid: 4, Max: 9
Min: 5, Mid: 7, Max: 9
Min: 8, Mid: 8, Max: 9
Min: 9, Mid: 9, Max: 9
Returned Value: 9
1.2).
Min: 2, Mid: 5, Max: 8
Min: 6, Mid: 7, Max: 8
Min: 6, Mid: 6, Max: 6
Min: 6, Max: 5
Returned Value: -1
2).
public class TestSort {
public static void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
// find index of smallest remaining value
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
// swap smallest value its proper place, a[i]
swap(a, i, min);
// code to print after each pass
System.out.println("After "+(i+1)+" pass, content of array - ");
printArray(a);
}
}
// Swaps a[i] with a[j].
public static void swap(int[] a, int i, int j) {
if (i != j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
public static void printArray(int arr[]){
for(int x: arr){
System.out.print(x+" ");
}
System.out.println();
}
public static void main(String[] args) {
int arr[] = { 7, 1, 6, 12, -3, 8, 4, 21, 2, 30, -1, 9 };
selectionSort(arr);
}
}
2.1)
After 1 pass, content of array -
-3 1 6 12 7 8 4 21 2 30 -1 9
After 2 pass, content of array -
-3 -1 6 12 7 8 4 21 2 30 1 9
After 3 pass, content of array -
-3 -1 1 12 7 8 4 21 2 30 6 9
After 4 pass, content of array -
-3 -1 1 2 7 8 4 21 12 30 6 9
After 5 pass, content of array -
-3 -1 1 2 4 8 7 21 12 30 6 9
After 6 pass, content of array -
-3 -1 1 2 4 6 7 21 12 30 8 9
After 7 pass, content of array -
-3 -1 1 2 4 6 7 21 12 30 8 9
After 8 pass, content of array -
-3 -1 1 2 4 6 7 8 12 30 21 9
After 9 pass, content of array -
-3 -1 1 2 4 6 7 8 9 30 21 12
After 10 pass, content of array -
-3 -1 1 2 4 6 7 8 9 12 21 30
After 11 pass, content of array -
-3 -1 1 2 4 6 7 8 9 12 21 30
2.2)
public class TestSort {
public static void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
// find index of smallest remaining value
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
// swap smallest value its proper place, a[i]
swap(a, i, min);
// code to print after each pass
System.out.println("After " + (i + 1)
+ " pass, content of array - ");
printArray(a);
}
}
// Swaps a[i] with a[j].
public static void swap(int[] a, int i, int j) {
if (i != j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
// Insertion sort
public static void insertionSort(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j - 1;
while ((i > -1) && (array[i] > key)) {
array[i + 1] = array[i];
i--;
}
array[i + 1] = key;
System.out.println("After each pass, content of array: ");
printArray(array);
}
}
// Bubble sort
public static void bubbleSort(int array[]) {
int n = array.length;
int k;
for (int m = n; m >= 0; m--) {
for (int i = 0; i < n - 1; i++) {
k = i + 1;
if (array[i] > array[k]) {
swap(array, i, k);
}
}
System.out.println("After each pass, content of array: ");
printArray(array);
}
}
// method to print array
public static void printArray(int arr[]) {
for (int x : arr) {
System.out.print(x + " ");
}
System.out.println();
}
public static void main(String[] args) {
int arr[] = { 7, 1, 6, 12, -3, 8, 4, 21, 2, 30, -1, 9 };
//selectionSort(arr);
System.out.println("************* Insertion Sort ***************");
insertionSort(arr);
//System.out.println(" ****************************Bubble Sort****************");
//bubbleSort(arr);
}
}
************************ Insertion sort Output step by step ****************************
************* Insertion Sort ***************
After each pass, content of array:
1 7 6 12 -3 8 4 21 2 30 -1 9
After each pass, content of array:
1 6 7 12 -3 8 4 21 2 30 -1 9
After each pass, content of array:
1 6 7 12 -3 8 4 21 2 30 -1 9
After each pass, content of array:
-3 1 6 7 12 8 4 21 2 30 -1 9
After each pass, content of array:
-3 1 6 7 8 12 4 21 2 30 -1 9
After each pass, content of array:
-3 1 4 6 7 8 12 21 2 30 -1 9
After each pass, content of array:
-3 1 4 6 7 8 12 21 2 30 -1 9
After each pass, content of array:
-3 1 2 4 6 7 8 12 21 30 -1 9
After each pass, content of array:
-3 1 2 4 6 7 8 12 21 30 -1 9
After each pass, content of array:
-3 -1 1 2 4 6 7 8 12 21 30 9
After each pass, content of array:
-3 -1 1 2 4 6 7 8 9 12 21 30
************************ Bubble sort step by step ***********************************
****************************Bubble Sort****************
After each pass, content of array:
1 6 7 -3 8 4 12 2 21 -1 9 30
After each pass, content of array:
1 6 -3 7 4 8 2 12 -1 9 21 30
After each pass, content of array:
1 -3 6 4 7 2 8 -1 9 12 21 30
After each pass, content of array:
-3 1 4 6 2 7 -1 8 9 12 21 30
After each pass, content of array:
-3 1 4 2 6 -1 7 8 9 12 21 30
After each pass, content of array:
-3 1 2 4 -1 6 7 8 9 12 21 30
After each pass, content of array:
-3 1 2 -1 4 6 7 8 9 12 21 30
After each pass, content of array:
-3 1 -1 2 4 6 7 8 9 12 21 30
After each pass, content of array:
-3 -1 1 2 4 6 7 8 9 12 21 30
After each pass, content of array:
-3 -1 1 2 4 6 7 8 9 12 21 30
After each pass, content of array:
-3 -1 1 2 4 6 7 8 9 12 21 30
After each pass, content of array:
-3 -1 1 2 4 6 7 8 9 12 21 30
After each pass, content of array:
-3 -1 1 2 4 6 7 8 9 12 21 30
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.