In this post we'll see how to write Quick sort program in Python. Quick sort is considered one of the most efficient algorithm and it is classified as "divide and conquer algorithm".
How does Quick sort algorithm work
Quick sort works as follows-
- Choose one of the array elements as pivot and then partition all the elements around that pivot.
- All the elements having value less than the pivot come before the pivot.
- All the elements having value higher than the pivot come after the pivot.
- Swap the pivot element with the first element of the higher values so that the pivot element is placed in between the lower and higher values.
Once the elements are partitioned around pivot you get two sub-arrays. One on the left of the pivot having values smaller than the pivot and another on the right of the pivot having values greater than the pivot. Steps 1-3 are executed recursively for these 2 sub-arrays.
One of the decisions you have to make while implementing Quick sort is what value should be chosen as pivot, options are-
- Pick the first element as a pivot
- Pick the last element as a pivot
- Pick any random element as a pivot
- Pick median of the array elements as a pivot
Most commonly, right most element (last element) is chosen as pivot. In the implementation given here last element is chosen as pivot.
Let's try to understand how partitioning works with the help of the following array.
Initialize a variable i to keep track of the index where elements smaller than the pivot will be placed. Then start with the leftmost element of the array and compare it with the pivot, if it is less than the pivot then swap it with the element at index i. Increment i by 1.
Once this comparison is done, Swap the pivot element with the first element of the higher values so that the pivot element is placed in between the lower and higher values. After pivot placement array can be visualized as given below.
Now, you can divide array into two subarrays around the pivot for further processing of choosing the last element in each sub-array as pivot and partitioning the array again using recursive calls.
Quick Sort Python program
def partition(array, low, high):
pivot = array[high]
i = low - 1
for j in range(low, high):
#get all the elements lower than pivot to the left side
if array[j] <= pivot:
i += 1
array[i], array[j] = array[j], array[i]
#bring pivot to its intended position so that all the elements on the
# left of pivot are less than it and on the right are greater than it
(array[i + 1], array[high]) = (array[high], array[i + 1])
return i+1
def quick_sort(arr, low, high):
#basecase for recursion
if(high - low <= 0):
return;
pivot_index = partition(arr, low, high)
# once the pivot is it in its right place
# divide the array in 2 parts and recursively call
# 2 parts to sort them
quick_sort(arr, low, pivot_index-1)
quick_sort(arr, pivot_index+1, high)
mylist = [64, -34, 25, 5, 22, 11, 0, 2, 105, 6, 22]
quick_sort(mylist, 0, len(mylist) - 1)
print('Sorted Array:', mylist)
Output
Sorted Array: [-34, 0, 2, 5, 6, 11, 22, 22, 25, 64, 105]
Quick sort using list comprehension
Another way to write quick sort program in Python is using list comprehension. By selecting a pivot and using list comprehension with a condition to check if list elements are less than the pivot or list elements are greater than the pivot, two separate lists can be created around the pivot.
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
#last element as pivot
pivot = arr[-1]
left = [a for a in arr[0:len(arr)-1] if a <= pivot]
right = [a for a in arr[0:len(arr)-1] if a > pivot]
return quick_sort_comp(left) +[pivot] +quick_sort_comp(right)
my_list = [64, -34, 25, 5, 22, 11, 0, 2, 105, 6, 22]
sort_list = quick_sort(my_list)
print('Sorted Array:', sort_list)
Output
Sorted Array: [-34, 0, 2, 5, 6, 11, 22, 22, 25, 64, 105]
Quick sort time and space complexity
Average and best case time complexity of Quick sort is O(n log n). In worst case, when pivot value doesn't partition elements properly, time complexity can be O(n2).
When implemented recursively extra space for recursive call method stacks is required so the worst case space complexity of Quick sort is O(n). While best and average case space complexity is O(log n).
That's all for the topic Quick Sort Python Program. If something is missing or you have something to share about the topic please write a comment.
You may also like
No comments:
Post a Comment