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 let’s learn to implement one more sorting algorithm which is QuickSort Algorithm.
Quicksort is an in-place sorting algorithm, 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 sorting algorithms, 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
QuickSort Algorithm – Code Visualization
Time Complexity Of QuickSort
| Best Case | O(n log n) |
| Average Case | O(n log n) |
| Worst Case | O(n2) |
Algorithm:
- Pick an element, called a pivot, from the array.
- 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 the partition operation.
- Recursively apply 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.
Output:
Feel free to look at some other algorithms here or some programs on lists here or have a look at all the programs on python here.