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]

Related Algorithms in Python

Free Spring Boot Tutorial - 5 Hours Full Course

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