### Quick Sort Algorithm in Python

In this source code example, we will write a code to implement the Quick Sort algorithm in Python.

Quicksort is a divide and conquer algorithm. To get the best performance, we would like to divide the sequence right down the middle into two equal-sized sequences. This would mean that we would have to pick the value exactly in the middle to be the pivot since the pivot is used to divide the two lists.

For quicksort to have O(n log n) complexity, like merge sort, it must partition the list in O(n) time. We must choose a pivot quickly and we must choose it well. If we don’t choose a pivot close to the middle, we will not get the O(n log n) complexity we hope for. It turns out that choosing a random pivot from the list is good enough.

# Quick Sort Algorithm in Python

In this Python program, we will take input from the User or console and print the result to the output:
``````# Quick sort in Python

# function to find the partition position
def partition(array, low, high):

# choose the rightmost element as pivot
pivot = array[high]

# pointer for greater element
i = low - 1

# traverse through all elements
# compare each element with pivot
for j in range(low, high):
if array[j] <= pivot:
# if element smaller than pivot is found
# swap it with the greater element pointed by i
i = i + 1

# swapping element at i with element at j
(array[i], array[j]) = (array[j], array[i])

# swap the pivot element with the greater element specified by i
(array[i + 1], array[high]) = (array[high], array[i + 1])

# return the position from where partition is done
return i + 1

# function to perform quicksort
def quickSort(array, low, high):
if low < high:

# find pivot element such that
# element smaller than pivot are on the left
# element greater than pivot are on the right
pi = partition(array, low, high)

# recursive call on the left of pivot
quickSort(array, low, pi - 1)

# recursive call on the right of pivot
quickSort(array, pi + 1, high)

if __name__ == "__main__":
user_input = input("Enter numbers separated by a comma:\n").strip()
data = [int(item) for item in user_input.split(",")]
size = len(data)
quickSort(data, 0, size - 1)
print('Sorted Array in Ascending Order:')
print(data)
``````

Output:

``````Enter numbers separated by a comma:
20,10,15,5,3,2,1
Sorted Array in Ascending Order:
[1, 2, 3, 5, 10, 15, 20]``````

# Free Spring Boot Tutorial - 5 Hours Full Course

Watch this course on YouTube at Spring Boot Tutorial | Fee 5 Hours Full Course