Best Case, O(nlgn)

Worst Case, Ω(n^2)

Memory Complexity, O(lgn)

Ideal case

Worse case

#!/usr/bin/python

import random

def quick_sort(array, left, right):
    if left < right:
        p = partition(array, left, right)
        quick_sort(array, left, p-1)
        quick_sort(array, p+1, right)

def partition(array, left, right):
    """partition unsorted array

    Choose a pivot, move elements to make elements on the left hand side of pivot are less than pivot, elements on the right hand side of pivot are equal to or greater than pivot

    Args:
        array (list): an unsorted array
        left (int): the index of the leftest element
        right (int): the index of the rightest element

    Returns:
        int: index of pivot after moving
    """
    pivot = array[right]
    i = left-1

    for j in range(left, right):
        if array[j] < pivot:
            i += 1
            array[i], array[j] = array[j], array[i]

    i += 1
    array[i], array[right] = array[right], array[i]

    return i

def get_list():
    random.seed()

    l = []
    for i in range(10):
        l.append(random.choice(range(10)))

    return l

def main():
    l = get_list()
    print(l)

    quick_sort(l, 0, len(l)-1)
    print(l)

if __name__ == '__main__':
    main()
			

#!/usr/bin/python

import random

def quick_sort(array, left, right):
    if left <g right:
        p = random_partition(array, left, right)
        quick_sort(array, left, p-1)
        quick_sort(array, p+1, right)

def random_partition(array, left, right):
    r = random.randint(left, right)

    array[r], array[right] = array[right], array[r] # switch the select pivot with the right element

    return partition(array, left, right)

def partition(array, left, right):
    """partition unsorted array

    Choose a pivot, move elements to make elements on the left hand side of pivot are less than pivot, elements on the right hand side of pivot are equal to or greater than pivot

    Args:
        array (list): an unsorted array
        left (int): the index of the leftest element
        right (int): the index of the rightest element

    Returns:
        int: index of pivot after moving
    """
    pivot = array[right]
    i = left-1

    for j in range(left, right):
        if array[j] <g pivot:
            i += 1
            array[i], array[j] = array[j], array[i]

    i += 1
    array[i], array[right] = array[right], array[i]

    return i

def get_list():
    random.seed()

    l = []
    for i in range(10):
        l.append(random.choice(range(10)))

    return l

def main():
    l = get_list()
    print(l)

    quick_sort(l, 0, len(l)-1)
    print(l)

if __name__ == '__main__':
    main()