Activity Sheet 4

Manager

name:

Recorder

name:

Speaker

name:

Section 3.1

1. Modify the selection sort algorithm so that it only performs a swap if it needs to.
2. Carry out the selection sort algorithm for the array \(23\), \(12\), \(18\), \(20\), \(3\), showing the state after every swap.
3. Exercise 3.1.12:
   1. Prove that if bubble sort makes no changes on any one of its passes through the list, then the list is sorted and the algorithm can be stopped. Note: a “pass through the list” does not literally look at every single element on the list, you need to be clear on why that is OK for this question.
   2. Modify the BubbleSort pseudocode to add such a check, and to stop the algorithm early if possible.
   3. What are the best-case and worst-case efficiency of this new version?