Quicksort with Python

def sort(array=[12,4,5,6,7,3,1,15]):    """Sort the array by using quicksort."""    less = []    equal = []    greater = []    if len(array) > 1:        pivot = array[0]        for x in array:            if x < pivot:                less.append(x)            elif x == pivot:                equal.append(x)            elif x > pivot:                greater.append(x)        # Don't forget to return something!        return sort(less)+equal+sort(greater)  # Just use the + operator to join lists    # Note that you want equal ^^^^^ not pivot    else:  # You need to handle the part at the end of the recursion - when you only have one element in your array, just return the array.        return array

Quick sort without additional memory (in place)

Usage:

array = [97, 200, 100, 101, 211, 107]quicksort(array)print(array)# array -> [97, 100, 101, 107, 200, 211]

def partition(array, begin, end):    pivot = begin    for i in range(begin+1, end+1):        if array[i] <= array[begin]:            pivot += 1            array[i], array[pivot] = array[pivot], array[i]    array[pivot], array[begin] = array[begin], array[pivot]    return pivotdef quicksort(array, begin=0, end=None):    if end is None:        end = len(array) - 1    def _quicksort(array, begin, end):        if begin >= end:            return        pivot = partition(array, begin, end)        _quicksort(array, begin, pivot-1)        _quicksort(array, pivot+1, end)    return _quicksort(array, begin, end)

There is another concise and beautiful version

def qsort(arr):    if len(arr) <= 1:        return arr    else:        return qsort([x for x in arr[1:] if x < arr[0]])        + [arr[0]]        + qsort([x for x in arr[1:] if x >= arr[0]])

Let me explain the above codes for details

1. pick the first element of array arr[0] as pivot

   [arr[0]]

2. qsort those elements of array which are less than pivot with List Comprehension

   qsort([x for x in arr[1:] if x < arr[0]])

3. qsort those elements of array which are larger than pivot with List Comprehension

   qsort([x for x in arr[1:] if x >= arr[0]])