Trusted answers to developer questions
How to implement QuickSort in Python
Educative Answers TeamQuickSort is an in-place sorting algorithm with worst-case time complexity of .
Implementation
QuickSort can be implemented both iteratively and recursively. We’ll mainly focus on the recursive implementation, as it is far more convenient, intuitive, and simplistic – iterative implementation is generally unrecommended. Arrays are used as an example here, but QuickSort can be implemented on other data structures (like linked lists) as well.
The algorithm can be broken down into three parts​​:
- Partitioning the array about the pivot.
- Passing the smaller arrays to the recursive calls.
- Joining the sorted arrays that are returned from the recursive call and the pivot.
1 of 16
In the above illustration, we used the first element of the array as a pivot, even though any of the elements could​ be taken​.
Code
def QuickSort(arr):
elements = len(arr)
#Base case
if elements < 2:
return arr
current_position = 0 #Position of the partitioning element
for i in range(1, elements): #Partitioning loop
if arr[i] <= arr[0]:
current_position += 1
temp = arr[i]
arr[i] = arr[current_position]
arr[current_position] = temp
temp = arr[0]
arr[0] = arr[current_position]
arr[current_position] = temp #Brings pivot to it's appropriate position
left = QuickSort(arr[0:current_position]) #Sorts the elements to the left of pivot
right = QuickSort(arr[current_position+1:elements]) #sorts the elements to the right of pivot
arr = left + [arr[current_position]] + right #Merging everything together
return arr
array_to_be_sorted = [4,2,7,3,1,6]
print("Original Array: ",array_to_be_sorted)
print("Sorted Array: ",QuickSort(array_to_be_sorted))RELATED TAGS
quicksort
python
sorting
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES
View all Courses
Keep Exploring
Related Courses
