The partition function is a function that takes in an array A[l..u] as input. Here, *l* is the lower bound, and *u *is the upper bound of the array. The algorithm finds an index *q *such that all elements less than A[q] fall in the subarray A[l..q-1], and all elements greater than A[q] fall in the subarray A[q+1..u]. The partition function achieves this by using a pivot element and two pointers – pointer i and pointer j to the array.

Pointer j points to the first element in the array, and the pointer i is initialized as j-1. The function iterates through the array using pointer j. For element A[j], the element can be greater than the pivot element or less than the pivot element. If the element is greater than the pivot element, pointer j gets incremented, pointing to the next element. If the element A[j] is less than the pivot element, we increment pointer i, swap A[i] and A[j]. The swapping of the elements helps maintain the pointer i such that the elements up to the element pointed by pointer i are less than the pivot element. As a final step, the partition function swaps the pivot element with the element at index i+1, thereby moving the pivot element in the correct position in the partitioned array.

**Source Code**

# The last element of the array is taken

# to be pivot element

pivot_elt = arr[ub-1]

i = lb - 1

for j in range(lb, ub):

# If the element is less than pivot element

if arr[j] <pivot_elt:

# Swap the elements so that the elements

# arr[lb..i] is always less than pivot element

i = i + 1

arr[i], arr[j] = arr[j], arr[i]

# Final swap of the pivot element and arr[i+1]

# to put the pivot element in place

arr[i+1], arr[ub-1] = arr[ub-1], arr[i+1]

return i+1

def quick_sort(arr, lb, ub):

if(lb<ub):

# Recursively sorting the array

q = partition(arr, lb, ub)

arr = quick_sort(arr, lb, q)

arr = quick_sort(arr, q+1, ub)

return arr

if __name__ == "__main__":

arr = [3, 7, 9, 2, 5, 0]

n = len(arr)

arr = quick_sort(arr, 0, n)

print (arr)

The best-case time complexity of quicksort is O(n log n). In the best-case scenario, in each call to the algorithm, the algorithm divides the problem into two subproblems of equal size. The worst time complexity of the quicksort algorithm is O(n^2). This occurs when the partition element is always chosen as the last element, and the array is already sorted.