Score array
- Algorithms course
- Intermediate
- Lesson 22/80
- 4 min
Put scores in an array and print them.
Apply merge sort
Now we add a function that sorts the score array with merge sort. The init_scores function comes from the previous lesson and is called here.
Recall that merge sort runs in O(n log n) and is stable. We will use the merge helper to combine the two sorted halves.
The expected sorted array is [78, 85, 88, 90, 92]; correctly sorted from smallest to largest.
merge helper
merge(left, right) combines two sorted arrays. This helper was introduced in earlier sections; we reuse it here.
With two pointers we append the smaller to the result. Leftovers are copied to the end. The result is one sorted array.
Without this helper merge sort cannot work; that is why we include it in the project.
Practice Sort scores
Write merge_sort_scores(scores). Print [78, 85, 88, 90, 92] with print(merge_sort_scores(init_scores())).
Starter code
def init_scores():
# Return score array
return [85, 92, 78, 90, 88]
def merge_sort_scores(scores):
# Sort scoresSample solution
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:]); result.extend(right[j:])
return result
def init_scores():
# Return score array
return [85, 92, 78, 90, 88]
def merge_sort_scores(scores):
# Sort scores
if len(scores) <= 1:
return scores
mid = len(scores) // 2
left = merge_sort_scores(scores[:mid])
right = merge_sort_scores(scores[mid:])
return merge(left, right)
print(merge_sort_scores(init_scores()))Expected output
[78, 85, 88, 90, 92]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What is the sorted array?
- [85, 92, 78, 90, 88]
- [92, 90, 88, 85, 78]
- [78, 85, 88, 90, 92] Correct answer
- [78, 88, 85, 90, 92]
Explanation: [78, 85, 88, 90, 92]
2 Base case
if len(scores) ____1:if len(scores) <=1:Explanation: <= is right.
3 Score array: match the terms
| Term | Meaning |
|---|---|
init_scores |
Data |
merge_sort_scores |
Sort |
merge |
Helper |
Result |
[78,85,88,90,92] |