# Selection Sort

##### Intuition

Learn how to perform selection sort yourself (without a computer) to develop a feel for the algorithm.

#### Intuition:

Selection sort finds the smallest value in the list and then swaps it with the value at position 0. It then looks from position 1 onwards for the second smallest value (the smallest is at position 0) and swaps that one with the one at position 1, does this for all remaining positions in the list.

##### Analysis

Analyze the runtime and memory usage of selection sort with big-O notation and see why it is a stable sort.

#### Analysis:

- Learn the basics of big-O notation
- Determine why selection sort uses
*O(n*or quadratic time in any case^{2}) - Determine why selection sort uses
*O(1)*or constant extra memory in any case, i.e. it works in-place. - Briefly discuss applications.

##### Song and Code

MEMORIZE selection sort by learning the musicAlgo, and see me use the lyrics to code the algorithm in Python.

#### Song and Code:

- Hear the 17-line, 90 second selection sort song:
- The first part covers big-O analysis facts.
- The second covers the pseudocode which will help you program selection sort in any programming language.

- Watch me demonstrate how to use the song lyrics to implement the algorithm in Python, the most straightforward programming language (in my opinion).

#### Intuition:

Selection sort finds the smallest value in the list and then swaps it with the value at position 0. It then looks from position 1 onwards for the second smallest value (the smallest is at position 0) and swaps that one with the one at position 1, does this for all remaining positions in the list.

#### Analysis:

- Learn the basics of big-O notation
- Determine why selection sort uses
*O(n*or quadratic time in any case^{2}) - Determine why selection sort uses
*O(1)*or constant extra memory in any case, i.e. it works in-place. - Briefly discuss applications.

#### Song and Code:

- Hear the 17-line, 90 second selection sort song:
- The first part covers big-O analysis facts.
- The second covers the pseudocode which will help you program selection sort in any programming language.

- Watch me demonstrate how to use the song lyrics to implement the algorithm in Python, the most straightforward programming language (in my opinion).