Selection sort is one of the familiar sorting algorithms. It is well suited for the situations where you are trying to minimize the moving of the data from one location to another.
Suppose you have an ArrayList of data of size s in which the first k elements are sorted, and every item in the unsorted part is greater than the largest item in the sorted part.
You would like to sort the rest of the ArrayList. We know how to swap two items in the ArrayList. So, if we can find the location of the smallest item in the unsorted part and swap it with the first item in the unsorted part, the sorted part will be one item bigger, and the unsorted part will be one item smaller.
If we repeat this until the last item is swapped into its correct position, we will have finished sorting the remainder of the ArrayList.
Here is an example:
>--- sorted ------< >--- unsorted ------------<
+----+----+----+----++----+----+----+----+----+----+
| 0 | 1 | 2 | 3 || 4 | 5 | 6 | 7 | 8 | 9 |
+----+----+----+----++----+----+----+----+----+----+
| 13 | 16 | 17 | 20 || 27 | 31 | 22 | 25 | 28 | 29 |
+----+----+----+----++----+----+----+----+----+----+
^
min unsorted
Swap elements at locations 4 and 6:
>-------- sorted ------< >--- unsorted -------<
+----+----+----+----+----++----+----+----+----+----+
| 0 | 1 | 2 | 3 | 4 || 5 | 6 | 7 | 8 | 9 |
+----+----+----+----+----++----+----+----+----+----+
| 13 | 16 | 17 | 20 | 22 || 31 | 27 | 25 | 28 | 29 |
+----+----+----+----+----++----+----+----+----+----+
^
min unsorted
Swap elements at locations 5 and 7:
>--------- sorted ----------< >--- unsorted ---<
+----+----+----+----+----+----++----+----+----+----+
| 0 | 1 | 2 | 3 | 4 | 5 || 6 | 7 | 8 | 9 |
+----+----+----+----+----+----++----+----+----+----+
| 13 | 16 | 17 | 20 | 22 | 25 || 27 | 31 | 28 | 29 |
+----+----+----+----+----+----++----+----+----+----+
^
min unsorted
Swap elements at locations 6 and 6:
>----------- sorted -------------< >- unsorted -<
+----+----+----+----+----+----+----++----+----+----+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 || 7 | 8 | 9 |
+----+----+----+----+----+----+----++----+----+----+
| 13 | 16 | 17 | 20 | 22 | 25 | 27 || 31 | 28 | 29 |
+----+----+----+----+----+----+----++----+----+----+
^
min unsorted
What about the case when none of the ArrayList is sorted? Well, then the sorted part has size 0, and the unsorted part starts at the index 0.
In the Algorithms class design the helper method findMinLoc that finds the location of the smallest item in the unsorted part of the given ArrayList.
Note: Think carefully through the first step of the design recipe, to make sure you know what the method consumes and what does it produce.
In the Algorithms class design the method selectionSort that implements the selection sort algorithm.
Design two Comparators for the Balloons, the BalloonsBySize that compares the balloons by their radius, and BalloonsByHeight that compares them by their distance to the top.
Test your sorting method and the helper method on lists of balloons using each of the two Comparators.