beyondgrader.com Logo
DemoBrowseAboutTeamLogin

Selection Sort

Geoffrey Challen // 2020.11.0

Create a named selectionSort that implements selection sort on a passed IntArray. To ensure that you are implementing selection sort, you should also return a List<Int> containing the positions of the minimum value on each pass through the array.

Selection sort works by repeatedly finding the smallest value in an array and moving it into position. In the first iteration, we find the smallest value of the entire array (starting at index 0) and swap it to the front. Next, we find the smallest value of the array starting at index 1 and swap it to position 1. This continues until the remaining array has size 1, at which point we are done.

To receive credit, you'll need to follow these instructions carefully:

  • If the passed array contains less than 2 values, throw an IllegalArgumentException.
  • On each pass through the array, find the minimum value, add its position (not its value) to the list of positions, and then swap it into place
  • Grow the sorted part from the left to the right: meaning that your first minimum loop should start at 0, the next at 1, etc
  • Finish when the array has only one value left, since it will be the maximum assuming you've done everything correctly. Don't add the position of this value to the list of positions, meaning that if the array has N values, the list of positions should have N - 1 values.
  • If there are multiple positions with the minimum value, you should record the first