# Selection Sort¶

*Written by PChan on 2017-04-13*

## Key Idea: Finding the Minimum¶

Before we look at the actual sorting algorithm, let us start with an algorithm for finding the index of
the minimum element in a list. Keep in mind that you cannot simply call `Collections.min()`

or make any
assumptions regarding the state of the given list.

Think over this simpler problem: Given a list of three elements, how would you determine the smallest of the three? Use the following list: [3, 1, 2]

**Answer:**

- Declare a temporary variable (we would name it currentValue)
- Start with the first element; set currentValue to the first element
- currentValue is now 3.

- Compare the second element to the currentValue. If the second element is smaller than the
currentValue, set currentValue to the second element
- Is 1 less than 3? Yes! So, set currentValue to 1.

- Compare the third element to the currentValue. If the third element is smaller than the currentValue,
set currentValue to the third element
- Is 2 less than 1? No, so leave currentValue alone.

- The minimum of the list is simply currentValue: 1!

Now generalize this approach to work with a list of n elements. How can we modify this approach to keep track of the index of the smallest element? Solve this last issue before proceeding to the next section.

## The General Algorithm¶

Selection sort involves repeatedly searching for the minimum element of the list and swapping it to the correct position.

- Use the algorithm discussed above to find the minimum element
- Swap that element with the first element of the list
- Find the next smallest element of the list (or the minimum element of the list starting from the first element)
- Swap that element with the second element of the list
- Repeat this process until you have place the n - 1 element in the correct spot where
*n*is the length of the list

## Exercises¶

Here are some questions to ponder over (in order of ascending difficulty):

- Is there a best case scenario? A worst case scenario?
- How many passes would you need to make to sort an array of size 10? 100? 1000?
- Determine the runtime of this algorithm. What is the ratio of the time it takes to sort the list and the size of the list?