Unit 6 Extra Credit
Searching and Sorting Extra Credit:
1) List: 5, 8, 11, 14, 19, 20, 25
a) How many comparisons would be needed to sort list in ascending order using selection sort? Show work.
b) How many comparisons would be needed to sort list in ascending order using insertion sort? Show work.
c) How many passes through the while loop (iterative one) will be made if binary search is run looking for 20? Show work.
d) How many comparisons would sequential search have to make looking for 20?
2) List: 6, 9, 5, 2, 8, 10, 14, 17, 3
a) How many comparisons would be needed to sort list in ascending order using selection sort? Show work.
b) How many comparisons would be needed to sort list in ascending order using insertion sort? Show work.
3) List: 17, 14, 10, 9, 8, 6, 5, 3, 2
a) How many comparisons would be needed to sort list in ascending order using selection sort? Show work.
b) How many comparisons would be needed to sort list in ascending order using insertion sort? Show work.
4) public void doSomething(int[] arr){
for (int i = 0; i < arr.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++)
if (arr[j] < arr[index])
index = j;
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
}
int[] x = {8, 11, 15, 17, 19, 24};
doSomething(x);
a) How many comparisons (namely if arr[j] < arr[index]) will be made?
b) How many swaps will be made? A swap is the following code segment:
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
5) public void mystery(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++)
{
int key = array[j];
int i = j;
while (i > 0 && array [i-1] > key ))
{
array [i+1] = array [i];
i--;
}
array[i] = key;
}
}
int[] a = {1,5,7,9,13,15,8};
mystery(a);
a) How many comparisions (namely: i > 0 && array [i-1] > key) will be made?
b) How many less comparisons would be made by using mystery(a) as opposed to doSomething(a)?
6)
public int search(int key, int[] data)
{
int low = 0;
int high = data.length - 1;
while(high >= low) {
int middle = (low + high) / 2;
if(data[middle] == key) {
return middle;
}
if(data[middle] < key) {
low = middle + 1;
}
if(data[middle] > key) {
high = middle - 1;
}
}
return -1;
}
int[] m = {3, 8, 11, 18, 23, 31, 44, 50, 63,90};
a) What would be returned by a call to search(m,63);
b) Trace low, mid, and high if search(8) was called.
c) Trace low, mid, and high if search(60) was called.
7) int[] m = {3, 8, 11, 18, 23, 31, 44, 50, 63,90};
In the respective best case, how many comparisons will be made to search m for a value using
a) sequential search b) binary search
In the respective worst case, how many comparisons will be made to search m for a value using
a) sequential search b) binary search
8) If we were searching a list of 800 Strings, in the worst case how many comparisons would need to be made to search the list using
a) sequential search b) binary search
List RW: 6, 9, 5, 2, 8, 10, 14, 17, 3
a) List each step of merge sort for RW. List the partitions going down to the base case and the partitions as it unwinds to a sorted list.
b) Implement the merge method that accepts two sorted String arrays and returns one sorted ArrayList of Strings.
public ArrayList<String> merge(String[] one, String[] two)