[5 marks] When an array is to be sorted, it may happen that some data values start out being in the same position where they should end up. For example, in the array which is originally:
45,-4,32,0
the 32 is right where it will be in the final sorted output:
-4,0,32,45
But as a particular sorting algorithm operates, it might (depending on the algorithm) move such an element out of the position where it belongs and move it back eventually.
Let’s say that a sorting algorithm respects fixedpoints if it never moves an element that is in its proper position, on any input.
Consider the following methods of sorting:
Selection sort. The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.
Eg: 4 3 2 1 → 1 3 2 4 → 1 2 3 4
Insertion sort. Insertion sort iterates over the array, consuming one input element each repetition, and grows a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Eg: 4 3 2 1 → 3 4 2 1 → 2 3 4 1 → 1 2 3 4
Which of the following statements are true?
⭕️ Insertion sort does not respect fixedpoints but selection sort does.
⭕️ Selection sort does not respect fixedpoints but insertion sort does.
⭕️ Neither insertion sort nor selection sort respects fixed points.
⭕️ Both insertion sort and selection sort respect fixed points.
Justify your answer. If you claim that a particular sorting method does not respect fixed points, then give an example. If you claim that an algorithm does respect fixed points, argue why.