

In [1]:

    
#%autosave 0
from IPython.core.display import HTML, display
display(HTML('<style>.container { width:100%; !important } </style>'))

Selection Sort

The algorithm selection sort is specified via two equations:

If $L$ is empty, $\texttt{sort}(L)$ is the empty list: $$ \mathtt{sort}([]) = [] $$
Otherwise, we compute the smallest element of the list $L$ and we remove the first occurrence of
this element from $L$. Next, the remaining list is sorted recursively. Finally, the smallest element is added to the front of the sorted list: $$ L \not= [] \rightarrow \mathtt{sort}\bigl(L\bigr) = \bigl[\texttt{min}(L)\bigr] + \mathtt{sort}\bigl(\mathtt{delete}(\texttt{min}(L), L)\bigr) $$



In [2]:

    
def sort(L):
    if L == []:
        return []
    x = min(L)
    return [x] + sort(delete(x, L))

The algorithm to delete an element $x$ from a list $L$ is formulated recursively. There are three cases:

If $L$ is empty, we could return the empty list: $$\mathtt{delete}(x, []) = [] $$ However, this case is really an error, because when we call $\texttt{delete}(x, L)$ we always assume that $x$ occurs in $L$.
If $x$ is equal to the first element of $L$, then the function delete returns the rest of $L$: $$ \mathtt{delete}(x, [x] + R) = R$$
Otherwise, the element $x$ is removed recursively from the rest of the list: $$ x \not = y \rightarrow \mathtt{delete}(x, [y] + R) = [y] + \mathtt{delete}(x,R) $$



In [3]:

    
def delete(x, L):
    if L == []:
        assert L != [], f'delete({x}, [])'
    if L[0] == x:
        return L[1:]
    return [L[0]] + delete(x, L[1:])



In [4]:

    
L = [3, 5, 7, 4, 8, 1, 2, 3, 11, 13, 2]
sort(L)









    Out[4]:





[1, 2, 2, 3, 3, 4, 5, 7, 8, 11, 13]



In [ ]: