Sorting Algorithm: Quick Sort

Quick Sort.py

#!/usr/bin/env python3

def partition(array, left, right):
	i = left - 1  # set i one less than left
	pivot = array[right]  # set as rightmost element

	for j in range(left, right):  # j keeps on going till the pivot
		if array[j] <= pivot:
			i += 1  # increment i and swap arr[i] and arr[j]
			array[j], array[i] = array[i], array[j]

	array[i+1], array[right] = array[right], array[i+1] # swap pivot with the i+1

	return i+1  # return the partition index

def quicksort(array, left, right):
	if left < right:  # double check whether left is smaller than right
		partition_index = partition(array, left, right)

		quicksort(array, left, partition_index-1) # sort the left of partition
		quicksort(array, partition_index+1, right)  # sort the right of partition


print("Enter the elements of the array")
a = [int(n) for n in input().split()] # take array input

l = 0
r = len(a) - 1

quicksort(a, l, r)

print(a)