thank you for answer three questions. 1. Given the following array (2 pts) intl]
ID: 3705194 • Letter: T
Question
thank you for answer three questions.
1. Given the following array (2 pts) intl] a 18, 16, 19, 3,14, 6 3; a) How are the contents of the array arranged after each pass of the selection sort? b) How are the contents of the array arranged after each pass of the insertion sort? 2. Given the following array (3 pts) intl] b 3, 5, 6, 8, 12, 13, 16, 17, 18, 20 ) What elements of the array are compared (in order) when searching for the number 18 using linear search? b) What elements are compared in order) when searching for 18 using binary search c) How many elements are compared when searching 2 using linear search? How many using binary search? 3. Given the following 2-D array (2 pts) nt[ nums2,3, (2, 4, 6, (3,1,9,. 14,5,633 a) How many rows does nums have? b) How many columns does nums have? c What is stored in nums[2][1]? d) What is stored in nums[I]o]?Explanation / Answer
1)
arr[] a= 18, 16, 19, 3, 14, 6
a)
Selection Sort
Pass 1
// Find the minimum element in arr[0...5]
// and place it at beginning
3 16 19 18 14 6
Pass 2
// Find the minimum element in arr[1...5]
// and place it at beginning of arr[1...5]
3 6 19 18 14 16
Pass 3
// Find the minimum element in arr[2...5]
// and place it at beginning of arr[2...5]
3 6 14 18 19 16
Pass 4
// Find the minimum element in arr[3...5]
// and place it at beginning of arr[3...5]
3 6 14 16 19 18
Pass 5
// Find the minimum element in arr[4...5]
// and place it at beginning of arr[4...5]
3 6 14 16 18 19
b)
insertion_sort(arr, n)
Loop from i = 1 to n-1.
Pick element arr[i] and insert it into sorted sequence arr[0…i-1]
notation - sorted array {}, unsorted array - []
initial array : [18, 16, 19, 3, 14, 6]
pass1: {18}, [16, 19, 3, 14, 6]
pass2: {16, 18}, [19, 3, 14, 6]
pass3: {16, 18, 19}, [3, 14, 6]
pass4: {3, 16, 18, 19}, [14, 6]
pass5: {3, 14, 16, 18, 19}, [6]
pass6: {3, 6, 14, 16, 18, 19}
2)
arr b= [3,5,6,8,12,13,16,17,18,20}
a) search element - 18
3,5,6,8,12,13,16,17,18 will be compared in linear search
b) binary search
pass 1 b[0-n]: index = n/2 = 10/2 = 5
b[5] = 13 < 18
pass 2 b[index+1:n] = b[6-9]
index = 6+9/2 = 7
b[7] = 17 < 19
pass 3 b[index+1:n] = b[8-9]
index = 8+9/2 = 8
b[8] = 18 element found
we have compared 13, 17 and 18 in binary search
c) Searching 2 using linear search - Since it is not given that array is sorted. 10 elements will be compared.
using binary search, array must be sorted.
pass 1 b[0-n]: index = n/2 = 10/2 = 5
b[5] = 13 > 2
pass 2 b[0:index -1] = b[0-4]
index = 0+4/2 = 2
b[2] = 6 > 2
pass 3 b[0:index-1] = b[0-1]
index = 0+1/2 = 0
b[0] = 3 element not found
total 3 elements compared using binary search
3. nums = {{1,2,3},{2,4,6},{3,1,9},{4,5,6}}
a) there are 4 rows
b) there are 3 columns
c) nums[2][1] = 1
d) nums[1][0] = 2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.