In [ ]:

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



# Quicksort

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 [ ]: