Sorting Algorithms in Depth

1 Describe how a quick sort works. 4

One mark for each of the following, to a maximum of 4.

• An item is chosen as the pivot
• The list is partitioned so that items smaller than the pivot are on one side and larger items on the other
• The pivot is then in its final position
• The same process is repeated recursively on each part until the parts have one item or none

Model answer. An item is chosen as the pivot. The list is partitioned, so that all the items smaller than the pivot are on one side of it and all the larger items on the other, which puts the pivot in its final position. The same process is then repeated recursively on each of the two parts, until each part has one item or none, at which point the whole list is sorted.

2 A quick sort uses the first item of the list as its pivot. State the two lists that are formed, and the position of the pivot, when the list [6, 3, 9, 1, 8, 4] is partitioned. 3

One mark for each of the following, to a maximum of 3.

• The items smaller than the pivot are 3, 1 and 4
• The items larger than the pivot are 9 and 8
• The pivot, 6, is placed between them, in position 3

Model answer. The pivot is 6. The items smaller than 6, in their original order, are 3, 1 and 4, and the items larger are 9 and 8. The pivot is placed between the two lists, so the arrangement is 3, 1, 4, then 6, then 9, 8, and 6 is now in its final position, index 3.

3 Write a recursive Python function called quick_sort that takes a list and returns a new list with the same items in ascending order. It must use the first item as the pivot. 4

One mark for each of the following, to a maximum of 4.

• Base case: a list of 0 or 1 items is returned as it is
• The first item is chosen as the pivot and the rest are split into smaller and larger lists
• The function calls itself on both the smaller and the larger list
• The results are joined with the pivot between them

def quick_sort(items):
    if len(items) <= 1:
        return items
    pivot = items[0]
    smaller = [x for x in items[1:] if x < pivot]
    larger = [x for x in items[1:] if x >= pivot]
    return quick_sort(smaller) + [pivot] + quick_sort(larger)

print(quick_sort([6, 3, 9, 1, 8, 4]))

4 Compare the merge sort and quick sort algorithms. 6

One mark for each of the following, to a maximum of 6.

• Both use divide and conquer, and both are O(n log n) on average
• The worst case of merge sort is still O(n log n)
• The worst case of quick sort is O(n squared), for example with a poor pivot on sorted data
• Merge sort needs O(n) extra memory for the merged lists, while quick sort can be done in place
• Merge sort is stable, but the usual in place quick sort is not
• A conclusion, such as quick sort being faster in practice for memory held data, but merge sort being better when the worst case must be avoided or a stable sort is needed

Model answer. Both are divide and conquer algorithms and both take O(n log n) time on average. The worst case of merge sort is still O(n log n), because it always splits into halves, whereas the worst case of quick sort is O(n squared), which happens when the pivot is repeatedly the smallest or largest item, as with the first item as pivot on data that is already sorted. Merge sort needs O(n) extra memory for the merged lists, while quick sort can be done in place and needs little extra memory. Merge sort is stable, so equal items stay in order, and the usual in place quick sort is not. Quick sort is often faster in practice for data held in memory, so it suits general use, but merge sort is the better choice when the worst case must be avoided, when the sort must be stable or when the data is too big to hold in memory.

5 A list of student records is sorted by name, and is then sorted again by grade using a stable sort. Explain what is meant by a stable sort, and what the order of the final list will be. 3

One mark for each of the following, to a maximum of 3.

• A stable sort keeps items with equal keys in their original relative order
• The final list is in order of grade
• Students with the same grade remain in alphabetical order of name

Model answer. A stable sort keeps items that have equal keys in the same relative order that they had before the sort. After the second sort the list is in order of grade, and students with the same grade are still in alphabetical order of name, because they were in that order before the second sort and the stable sort did not change it.