Quicksort in Python: An Animated Approach

Create the wonderfully fast quicksort algorithm in Python! This video helps you grasp the quicksort algorithm intuitively through colorful animations and simple explanations. The main quicksort function and the partition function (using Lomuto's partitioning scheme) are both written, with algorithm visualizations given every step of the way.

Quicksort is an efficient, unstable sorting algorithm with O(n log n) run-time and minimal extra space requirements. It's a great algorithm to learn for any student of computer science and data structures and algorithms/DSA, or for those preparing for technical interviews.

Thank you for watching, and please let me know any questions you have in the comments!

CORRECTION: If you're going to run this or write for yourself, use the code at the end or the code in the pinned comment. In the section of the video on the partition function, the last two lines are under-indented by two spaces, but it is correct at the end and in the pinned comment.

Full quicksort playlist:

More detail on Lomuto's partitioning scheme and introduction to quicksort algorithm:

How to choose the pivot in quicksort (animated!):

[CodeSlate]

# Here's the Python code, as promised!
# Note that this Python is indented by two spaces, not the typical four,
# in order to match with the video.
def quicksort(array, low, high):
if high <= low:
return
initial_pivot_pos = (low + high)//2
final_pivot_pos = partition(array, low, high, initial_pivot_pos)
quicksort(array, low, final_pivot_pos - 1)
quicksort(array, final_pivot_pos + 1, high)

def partition(array, low, high, initial_pivot_pos):
array[initial_pivot_pos], array[high] = array[high], array[initial_pivot_pos]
final_pivot_pos = low
for i in range(low, high):
if array[i] <= array[high]:
array[final_pivot_pos], array[i] = array[i], array[final_pivot_pos]
final_pivot_pos += 1
array[high], array[final_pivot_pos] = array[final_pivot_pos], array[high]
return final_pivot_pos

[slearl]

I don't seem to get the correct result with the following code:

def quickSort(array, low, high):
if high <= low:
return
initial_pivot_pos = (low + high) // 2
final_pivot_pos = partition(array, low, high, initial_pivot_pos)
quickSort(array, low, final_pivot_pos - 1)
quickSort(array, final_pivot_pos + 1, high)

def partition(array, low, high, initial_pivot_pos):
array[initial_pivot_pos], array[high] = array[high], array[initial_pivot_pos]
final_pivot_pos = low
for i in range(low, high):
if array[i] <= array[high]:
array[final_pivot_pos], array[i] = array[i], array[final_pivot_pos]
final_pivot_pos += 1
array[high], array[final_pivot_pos] = array[final_pivot_pos], array[high]
return final_pivot_pos

numbers = [114, 70, 2, 8, 1, 3, 5, 6, 101, 99, 7]
n = len(numbers)
quickSort(numbers, 0, n - 1)
print("Sorted numbers:", numbers)

output -> Sorted numbers: [3, 7, 2, 5, 1, 6, 70, 101, 99, 8, 114]