Quick Sort Program in Python - Examples

Python - Quick Sort

In the tutorial, we will implement Quick Sort Algorithm in Python.

We will write a function named quick_sort() which takes list as argument and sorts this list using Quick Sort algorithm. Also, by default, this quick_sort() function sorts the list in ascending order. To get the descending order, all you have to do is just reverse the list.

Python Program

def quick_sort(alist, start, end):
    #Sorts the list from indexes start to end - 1 inclusive
    if end - start > 1:
        p = partition(alist, start, end)
        quick_sort(alist, start, p)
        quick_sort(alist, p + 1, end)
 
 
def partition(alist, start, end):
    pivot = alist[start]
    i = start + 1
    j = end - 1
 
    while True:
        while (i <= j and alist[i] <= pivot):
            i = i + 1
        while (i <= j and alist[j] >= pivot):
            j = j - 1
 
        if i <= j:
            alist[i], alist[j] = alist[j], alist[i]
        else:
            alist[start], alist[j] = alist[j], alist[start]
            return j

#input list
alist = [1, 74, 96, 5, 42, 63]
print('Input List\n', alist)

#sort list
quick_sort(alist, 0, len(alist))
print('Sorted List\n', alist)

Output

Input List
 [1, 74, 96, 5, 42, 63]
Sorted List
 [1, 5, 42, 63, 74, 96]

Conclusion

In this tutorial of Python Examples, we learned how to implement Quick Sort algorithm in Python.