Week 6 - ‘Recursive sorting’ and 4.1 ‘Dividing and conquering’. Flashcards
Summarise in your own words how the merge sort algorithm works.
In the merge sort algorithm, the list is recursively split into smaller and smaller parts. These parts are then stuck back together again using a merging process that ensures sorted order.
What is the complexity of the merge sort algorithm?
The complexity of merge sort is O(n log n), provided the slice operator can be eliminated. However, our idea is simply to present the main idea of merge sort, so we leave this possibility as an advanced exercise.
In the quick sort algorithm what is the role of the pivot value and split point?
- A quick sort first selects a value called the pivot value, its role is to assist with splitting the list.#
- The actual position where the pivot value belongs in the final sorted list, commonly called the split point, will be used to divide the list for subsequent calls to the quick sort.
Summarise in your own words the main ideas underlying how the quick sort algorithm works.
Quick sort relies on a partitioning process in which a value is selected from the list and assigned to a variable pivotValue. Two pointers, leftmark and rightmark, are then progressively moved rightwards from the beginning, and leftwards from the end of the list. As the pointers move towards one another, items indicated by the left pointer that are greater than pivotValue are swapped with items indicated by the right pointer that are less than pivotValue.
When the pointers cross, the list is split into two partitions at the position at which the pointers have met, and quick sort is recursively performed on each of these two partitions.
What is the complexity of the algorithm?
The complexity of quick sort is O(n log n).
it is sometimes considered better than a merge sort because it requires lee/no memory to store values during run-time.
What is the worst case for quick sort and what complexity does it have? Why?
The worst case for quick sort is when the pivot chosen at each step happens to be the largest or smallest item in the partition. The two new partitions formed will then be 0 and n − 1 items long. At the next step, sorting the partition of n − 1 items, picking the largest or smallest item as pivot, produces partitions of size 0 and one of size n − 2, … and so on. In this way, the list has to be split n times, and quick sort’s performance is then O(n2). It will also mean that the recursive version will require more memory for its stack, making the algorithm even less efficient.
