Quick Sort Algorithm in Python

Quick sort is a very efficient and commonly used sorting algorithm. Quick sort algorithm recursively breaks a larger list into two smaller lists in two phases at each step:

  1. partition phase
  2. sort phase

In quick sort, we first select a pivot value around which the list is to be divided into two smaller lists.Ideally the pivot value should be the middle value of the list. If however it is difficult to ascertain the middle value, we can take any item from the list to be the pivot.

In our code example below we select the first item in the list as pivot. We then partition the list to be sorted into two groups( named ‘prior’ for elements before the pivot and ‘after’ for elements after the pivot).

We then call the quick sort procedure recursively with the base case being equal to an empty list. The python code for quick sort algorithm is as follows:

def quick_sort(lst):
	if lst == []: 
        return []
        pivot = lst[0]
        prior = quick_sort([x for x in lst[1:] if x < pivot])
        after = quick_sort([x for x in lst[1:] if x >= pivot])
        return prior + [pivot] + after