# Selection Sort

Selection sort is the last simplistic sorting algorithms covered here1. It works by repeatedly searching for the next minimum value and moving it to the correct position. It’s difficult to describe with prose; however, it’s the easiest sorting algorithm to implement. Examine the animated image below in conjunction with the supplied pseudo code to understand it’s inner working.

Recall that bubble and insertion sort are $\Omega(n)-O(n^2)$ algorithms. When the data is pre-sorted the number of operations is linear to the input size. In the worst case scenario, reverse sorted data, the number of operations is $n^2$. Conversely, selection sort is $\Theta(n^2)$: the number of operations is the same regardless of the input data. One would assume that selection sort is inferior based on this data. However, recall that the RAM model weights all operations equally. The innovation of selection sort is that while the number of comparison operations is commiserate, the number of copy operation is minimized.

In this context, a copy is defined as copying data from one memory location to another. The pseudo code below demonstrates the three copy operations2 associated with swapping two array values.

int temp;

temp = A[i]; // 1st copy
A[i] = A[j]; // 2nd copy
A[j] = temp; // 3rd copy


Selection sort may outperform other simplistic sort algorithms owing to fewer copy operations. This is an important attribute to keep in mind for situations where moving data is expensive.

## Pseudo Code

\begin{algorithm}
\caption{Selection Sort}
\begin{algorithmic}
\REQUIRE $A$ = list of numbers
\ENSURE $A$ sorted in sequential order
\FUNCTION{selectionSort}{$A$}
\FOR{i $\gets$ 0 to ($\vert A \vert$ - 1)}
\STATE lowest $\gets$ i
\STATE
\FOR{j $\gets$ (i + 1) to ($\vert A \vert$ - 1)}
\IF{$A_{\text{lowest}} \gt A_j$ }
\STATE lowest $\gets$ j
\ENDIF
\ENDFOR
\STATE
\STATE swap $A_{\text{lowest}}$ and $A_i$
\ENDFOR
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}


## Asymptotic Complexity

$\Theta(n^2)$

Full Repo

Relevant Files:

## Exercises

1. Assume line 6 of the selection sort pseudo code is changed to:
$\text{if} \space A_{\text{lowest}} \lt A_j$
How does this change the final state?

The data will be sorted in descending order rather than ascending order.
2. Using the programming language of your choice, implement a selection sort function that accepts:

See the C implementation provided in the links below. Your implementation may vary significantly and still be correct.
- selection_sort.h
- selection_sort.c
- selection_sort_test.c

3. At this point, you should have implemented bubble, insertion, and selection sort. Instrument each of your algorithms to calculate the total number of copy and comparison operations. Next, sort the data contained in the sort.txt file and determine the total number of copy and comparison for each algorithm.

    Bubble Sort: copy = 71,844,390 comparisons = 49,988,559 total = 121,832,949