Quick Sort in Python

Introduction to Quick Sort in Python

In python, Quick sort is defined as a sorting algorithm which follows the divide and conquer method to select the pivot element based on which the remaining array will be divided into two sub-arrays elements which are less than pivot will be in 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 which is better than similar algorithms if it is implemented well. It has an average-case time complexity of O(NlogN) and 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 in the left side and all the elements of the list which are greater than pivot will be in 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 pivot element and start as starting off the list and end as the end of 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 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 its sorted positions.

So by following the above logic, we can implement the quick sort and this is one of the ways of implementation of quick sort which has an average case time complexity of O(NlogN) and worst case time complexity being O(n2). If we observe 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:

defpartition(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
defquicksort(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 first element as pivot element.

Code:

defpartition(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
defquicksort(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 starting element of the list and quick sort() function is similar as the first method of implementation where we will call sub-lists recursively and 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, what is the logic behind quick sort implementation with step by step explanation, and how quick sort can be implemented using various methods in python with examples and corresponding outputs.

This is a guide to Quick Sort in Python. Here we discuss the introduction to Quick Sort, logic behind quick sort and examples. You may also have a look at the following articles to learn more –

1. Merge Sort in Python
2. Priority Queues in Python
3. Python Map Function
4. Python Pandas Join