Introduction to Quick Sort in Python
In python, Quick sort is defined as a sorting algorithm that follows the divide and conquers method to select the pivot element based on which the remaining array will be divided into two sub-arrays elements that are less than pivot will be in the left sub-array and elements which are greater than pivot will be in right sub-array and the process will repeat recursively until all sub-arrays got sorted without using auxiliary array’s or extra space is called Quick sort. Quick sort is an efficient and most used sorting algorithm that is better than similar algorithms if implemented well. It has an average-case time complexity of O(NlogN), and the worst-case time complexity is O(n^2).
Logic behind Quick Sort in Python
Quick sort algorithm is an in-place sorting algorithm without the need of extra space or auxiliary array as all operations will be done in the same list, as we divided the given list into three parts as pivot element, elements less than pivot as a one sub-list and elements greater than pivot as another sub-list. This is also called as a partition-exchange sort. The quicksort is better sorting algorithm and, in most programming languages, available as a built-in sorting algorithm.
Given below are the main steps for the logic of quick sort implementation:
1. First, we will select the pivot element from the given list.
We can select the pivot element in different ways as below:
- We can select the first element of the list as a pivot.
- We can select the last element of the list as a pivot.
- We can select some random element of the list as a pivot.
- Finally, we can select the median of the elements of the list as a pivot.
2. In partitioning, we will rearrange the list in such a way that all the elements of the list which are less than pivot will be on the left side, and all the elements of the list which are greater than pivot will be on the right side, and same elements will be on any one of the sides of the pivot. This process is called partitioning. After the end of the partition process, the pivot element will be in its final position on the list.
3. We will apply the above steps recursively on both sub-arrays until all the sub-arrays are sorted.
Example:
Take a list with 6 elements as 9 7 15 10 2 5. Here we will take the first element of the list as a pivot element and start off the list and end the list.
Step 1: Pivot = 9 start = 9 end = 5
9 7 15 10 2 5
Now we will call the partitioning process on the given list, and we will get rearranged list with the pivot element being in its final position as below:
5 7 2 9 15 10
As we are seeing pivot element is in its final sorted position. Now we will apply the same steps to the left and right sub-lists of the pivot element.
Step 2: pivot = 5 start = 5 end =2 ( left sub-list)
2 5 7
pivot = 15 start = 15 end = 10 (right sub-list)
10 15
In the above step, we have called the partitioning method on both left and right sub-lists, and we got the re-arranged as below:
2 5 7 9 10 15
If we observe the list which we got in the above step, all elements are in their sorted positions.
By following the above logic, we can implement the quick sort, and this is one of the ways of implementing a quick sort with an average case time complexity of O(NlogN) and worst-case time complexity being O(n2). If we observe the above, sorting is happened in-place without using any extra space.
Examples of Quick Sort in Python
Given below are the examples:
Example #1
Quick sort implementation using the last element of the list as a pivot element.
Code:
def partition(my_arr, start, end):
pivot = my_arr[end]
i = start -1
for j in range(start, end):
if my_arr[j]<=pivot:
i=i+1
my_arr[i], my_arr[j] = my_arr[j], my_arr[i] my_arr[i+1], my_arr[end] = my_arr[end], my_arr[i+1] return i+1
def quicksort(my_arr, start, end):
if start<end:
q = partition(my_arr, start, end)
quicksort(my_arr, start, q-1)
quicksort(my_arr, q+1, end)
arr = [15, 9, 11, 2 ,21,12]
quicksort(arr, 0, 5)
print(arr)
In the above implementation, we have defined two functions, partition() and quick sort(), where partition function will do the operations on the list to re-arrange the list such that pivot element will be in sorted position, quick sort() function will divide the list into sub-lists and calls the partition function recursively such that all sub-lists will get sorted.
Output:
Example #2
Implementation of quick sort using the first element as the pivot element.
Code:
def partition(my_arr, start, end):
pivot = my_arr[start]
low = start+1
hight = end
while True:
while low <=high and my_arr[high] >= pivot:
high = high -1
while low <= high and my_arr[low] <= pivot:
low = low -1
if low <= high:
my_arr[low], my_arr[high] = my_arr[high], my_arr[low]
else:
break
my_arr[start], my_arr[high]= my_arr[high], my_arr[start] return high
def quicksort(my_arr, start, end):
if start<end:
q = partition(my_arr, start, end)
quicksort(my_arr, start, q-1)
quicksort(my_arr, q+1, end)
arr = [15, 9, 11, 2 ,21,12,7]
quicksort(arr, 0, 6)
print(arr)
In the above quick sort implementation, we have taken pivot as the starting element of the list. The quick sort() function is similar to the first method of implementation, where we will call sub-lists recursively, and the partition() function is modified based on the pivot element.
Output:
Conclusion
Finally, it is all about a quick sort algorithm in python. So far, we have seen the definition of quick sort, the logic behind quick sort implementation with step-by-step explanation, and how quick sort can be implemented using various python methods with examples and corresponding outputs.
Recommended Articles
This is a guide to Quick Sort in Python. Here we discuss the introduction to Quick Sort, the logic behind quick sort and examples. You may also have a look at the following articles to learn more –
