

In [ ]:

    
%%HTML
<style>
.container { width:100% } 
</style>

The basic idea of quick sort is as follows:

If the list $\mathtt{L}$ that is to be sorted is empty, we return $\mathtt{L}$: $$ \mathtt{sort}([]) = L $$
Otherwise, we have $\mathtt{L} = [\mathtt{x}] + \mathtt{R}$. In this case, we split $\mathtt{R}$ into two lists $\mathtt{S}$ and $\mathtt{B}$.
- The list $\mathtt{S}$ (the letter $\mathtt{S}$ stands for $\underline{s}\textrm{mall}$) contains all those elements of $\mathtt{R}$ that are less or equal than $\mathtt{x}$, we have: $$ \mathtt{S} := [\mathtt{y} \in \mathtt{R} \mid \mathtt{y} \leq \mathtt{x}] $$
- The list $\mathtt{B}$ (the letter $\mathtt{B}$ stands for $\underline{b}\textrm{ig}$) contains those elements of $\mathtt{R}$ that are bigger than $\mathtt{x}$, we have: $$ \mathtt{B} := [\mathtt{y} \in \mathtt{R} \mid \mathtt{y} > \mathtt{x}] $$
The process of splitting the list $\mathtt{R}$ into the lists $\mathtt{S}$ and $\mathtt{B}$ is called partitioning. After partitioning the list $\mathtt{R}$ into the lists $\mathtt{S}$ and $\mathtt{B}$, these lists are sorted recursively. Then, the result is computed by putting $\mathtt{x}$ between the lists $\mathtt{sort}(\mathtt{S})$ and $\mathtt{sort}(\mathtt{B})$: $$\mathtt{sort}([\mathtt{x}|\mathtt{R}]) = \mathtt{sort}(\mathtt{S}) + [\mathtt{x}] + \mathtt{sort}(\mathtt{B})$$



In [ ]:

    
def sort(L):
    if L == []:
        return L
    x, R = L[0], L[1:]
    S = [y for y in R if y <= x]
    B = [y for y in R if y >  x]
    return sort(S) + [x] + sort(B)



In [ ]:

    
sort([7, 8, 11, 12, 2, 5, 3, 7, 9, 3, 2])



In [ ]:

Quicksort