Scenario

Selection sort is best understood by imagining that you have two lists, A and B. Initially, we have list A, containing all the unsorted elements, and list B is empty. The idea is to use B to store the sorted elements. The algorithm would work by finding the smallest element from A and moving it to the end of B. We keep on doing this until A is empty and B is full. Instead of using two separate lists, we can just use the same input array, but keeping a pointer to divide the array in two.

In real life, this can be explained by picturing how you would sort a deck of cards. Using a shuffled deck, you can go through the cards one by one until you find the lowest card. You set this aside as a new, second pile. You then look for the next-lowest card and once found, you put it at the bottom of the second pile. You repeat this until the first pile is empty.

One way to arrive at the solution is to first write the pseudocode that uses two arrays (A and B, in the preceding description). Then, adopt the pseudocode to store the sorted list (array B) in the same input array by using the swapping method.

Aim

Implement the selection sort in Java

Prerequisites

• Implement the sort method found in the following class, which is available on the GitHub repository for the book at the following path: 
  https://github.com/TrainingByPackt/Data-Structures-and-Algorithms-in-Java/blob/master/src/main/java/com/packt/datastructuresandalg/lesson2/activity/selectionsort/SelectionSort.java
• The sort method should accept an integer array and sort it

Steps for Completion

1. Split the input array in two by using an array index pointer
2. The sort method should accept an integer array and sort it
3. Iterate over the unsorted portion of the array to find the minimum
4. The minimum item is then swapped so that it can be added to the end of the sorted portion