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]