QuickSort is an in-place sorting algorithm with worst-case time complexity of .
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​​:
In the above illustration, we used the first element of the array as a pivot, even though any of the elements could​ be taken​.
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
View all Courses