# Quicksort

# Quicksort

Implementation of the quicksort algorithm. This divide and conquer algorithm works by splitting up the problem by:

- Splitting up the problem in a base case (empty or element 1)
- Subdividing the problem until you end up in one of the base cases

Solution is not optimal, construction of lesser and greater could be done in place I believe.

```
def quicksort(arr):
# base case [] or [.]
if len(arr) < 2:
return arr
# otherwise choose pivot and recurse
pivot = arr[0]
lesser = [i for i in arr[1:] if i <= pivot]
greater = [i for i in arr[1:] if i >= pivot]
return quicksort(lesser) + [pivot] + quicksort(greater)
quicksort([1, 2, 1, 0, 1, 2, 3, 4])
```

```
[0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4]
```