Further Reading
You can find out more about the Collatz sequence on Wikipedia at
https://en.wikipedia.org/wiki/Collatz_conjecture. There are videos on YouTube about the sequence on the
Veritasium channel titled ―The Simplest Math Problem No One Can Solve - Collatz Conjecture‖ at
https://youtu.be/094y1Z2wpJg and and the Numberphile channel titled ―UNCRACKABLE? The
Collatz Conjecture‖ at https://youtu.be/5mFpVDpKX70.
123
E X E R C I S E # 4 0 : M E R G I N G T W O S O R T E D
L I S T S
mergeTwoLists([1, 3, 6], [5, 7, 8, 9])
→
[1, 3, 5, 6, 7, 8, 9]
One of the most efficient sorting algorithms is the merge sort algorithm. Merge sort has two
phases: the dividing phase and the merge phase. We won’t dive into this advanced algorithm in this
book. However, we can write code for the second half: merging two pre-sorted lists of integers into a
single sorted list.
Exercise Description
Write a mergeTwoLists() function with two parameters list1 and list2. The lists of
numbers passed for these parameters are already in sorted order from smallest to largest number. The
function returns a single sorted list of all numbers from these two lists.
You could write this function in one line of code by using Python’s sorted() function:
return sorted(list1 + list2)
But this would defeat the purpose of the exercise, so don’t use the sorted() function or
sort()
method as part of your solution.
These Python assert statements stop the program if their condition is False. Copy them to
the bottom of your solution program. Your solution is correct if the following assert statements’
conditions are all True:
assert mergeTwoLists([1, 3, 6], [5, 7, 8, 9]) == [1, 3, 5, 6, 7, 8, 9]
assert mergeTwoLists([1, 2, 3], [4, 5]) == [1, 2, 3, 4, 5]
assert mergeTwoLists([4, 5], [1, 2, 3]) == [1, 2, 3, 4, 5]
assert mergeTwoLists([2, 2, 2], [2, 2, 2]) == [2, 2, 2, 2, 2, 2]
assert mergeTwoLists([1, 2, 3], []) == [1, 2, 3]
assert mergeTwoLists([], [1, 2, 3]) == [1, 2, 3]
Try to write a solution based on the information in this description. If you still have trouble
solving this exercise, read the Solution Design and Special Cases and Gotchas sections for
additional hints.
Prerequisite concepts: lists, while loops, Boolean operators, append(), for loops, range()
with two arguments, len()
Python Programming Exercises, Gently Explained
124
Dostları ilə paylaş: |
