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
# 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
- Write a Python program for Linear Search and Binary Search
- Selection Sort Algorithm in Python
- Bubble Sort Algorithm in Python
- Bogo Sort Algorithm in Python
- Bucket Sort Algorithm in Python
- Comb Sort Algorithm in Python
- Counting Sort Algorithm in Python
- Heap Sort Algorithm in Python
- Insertion Sort Algorithm in Python
- Merge Sort Algorithm in Python
- Quick Sort Algorithm in Python
- Shell Sort Algorithm in Python
- Interpolation Search Algorithm in Python
Free Spring Boot Tutorial - 5 Hours Full Course
Watch this course on YouTube at Spring Boot Tutorial | Fee 5 Hours Full Course