Read sections 4.3-4.5 in chapter 4 and sections 5.1-5.6 in chapter 5 of the textbook Explorations in Computing.
def swap(list, x, y) # swaps the elements in list at index x and index y temp = list[x] list[x] = list[y] list[y] = temp end def bubsort(list) n = list.length for i in (1..n-1) do for j in (0..n-2) do # swap adjacent elements if they're not in correct order if list[j] > list[j+1] then swap(list, j, j+1) end end end end
Your trace should look like the table below. We've filled in the first two rows for you.
i j list 1 0 [4,7,3,6,1] 1 1 [4,3,7,6,1] 1 2 1 3 2 0 2 1 ...etc...
Merge Sort Algorithm:
1. Sort the first half of the array using merge sort.
2. Sort the second half of the array using merge sort.
3. Merge the two sorted halves to get a sorted array.
def f(n) if n == 0 || n == 1 then return n else return f(n-2) + f(n/2) end end
Trace the computation of f(7) by drawing a recursion tree (like the one we drew for Fibonacci numbers), showing all of the recursive computations that need to be computed to find the value for f(7).
1. If the list is empty, then the number of odd integers in the list is 0.
2. Otherwise, if the first element is odd, then the number of odd integers in the list is 1 + the number of odd integers in the rest of the list.
3. Otherwise the first element must be even, so the number of odd integers in the list is the number of odd integers in the rest of the list.
Complete the Ruby function below to perform this computation recursively:
def countodd(list) if ________________________ then return 0 end if ____________________________________ then return 1 + ___________________________________ else return ____________________________________ end end
For example, if we want to sort the list
list = [58, 82, 27, 18, 90, 84, 41, 56, 33]we create two lists, separating the elements based on the pivot 58:
list1 = [27, 18, 41, 56, 33] list2 = [82, 90, 84]
Each sublist is sorted (recursively):
list1 = [18, 27, 33, 41, 56] list2 = [82, 84, 90]
and the final result is
[18, 27, 33, 41, 56] + [58] + [82, 84, 90] ==> [18, 27, 33, 41, 56, 58, 82, 84, 90]
Consider the quick sort algorithm sorting a list of n integers.