QuickSort Algorithm in Python

Hello everyone,welcome back to programminginpython.com. Here I will show you how to implement QuickSort Algorithm in Python. In previous posts, I have covered Insertion Sort, Merge Sort, Selection Sort, and Bubble Sort. Now lets learn to implement one more sorting algorithm which is QuickSort Algorithm.

Quicksort is an in-place sortingalgorithm, which means it does not require any extra/temporary list to perform sorting, everything will be done on the original list itself. Here in this sorting technique we will select a pivot element and arrange all the items to the right are greater than pivot and elements to the left are lesser than the pivot. Again we do the same step for the left and right elements of the pivot as sublists until all the elements are sorted.

Quicksort when implemented well it is one of the best sortingalgorithms, In fact, the sort function provided in most of the language libraries is the implementation of Quicksort itself.

You can also watch the video on YouTube here.

See the below animation of Quicksort implementation,

By en:User:RolandH, CC BY-SA 3.0, Link

Time Complexity Of QuickSort

Program on Github

Algorithm:

1. Pick an element, called apivot, from the array.
2. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called thepartitionoperation.
3. Recursivelyapply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Program:

def partition(sort_list, low, high):

    i = (low -1)
    pivot = sort_list[high]
    for j in range(low, high):
        if sort_list[j] <= pivot:
            i += 1
            sort_list[i], sort_list[j] = sort_list[j], sort_list[i]
    sort_list[i+1],sort_list[high] = sort_list[high], sort_list[i+1]
    return (i+1)

            
def quick_sort(sort_list, low, high):
    if low < high:
        pi = partition(sort_list, low, high)
        quick_sort(sort_list, low, pi-1)
        quick_sort(sort_list, pi+1, high)


lst = []
size = int(input("Enter size of the list: "))

for i in range(size):
    elements = int(input("Enter an element"))
    lst.append(elements)

low = 0
high = len(lst) - 1
quick_sort(lst, low, high)

print(lst)

That is it guys, we have now successfully implemented Quick Sort Algorithm.

Program on GitHub

Output:

[QuickSort Algorithm in Python]QuickSort Algorithm in Python

Feel free to look at some otheralgorithmshereor some programs onlistshereor have a look atall the programson pythonhere.