Learn Data Structures and Algorithms in Python: Quick Sort

Explainer Video

Click to play video

Pseudocode

Select a "pivot" element - We'll arbitrarily choose the last element in the list
Move through all the elements in the list and swap them around until all the numbers less than the pivot are on the left, and the numbers greater than the pivot are on the right
Move the pivot between the two sections where it belongs
Recursively repeat for both sections

Assignment

We now have two sorting algorithms on our LockedIn backend! It is a bit annoying to maintain both in the codebase. Quicksort is fast on large datasets just like merge sort, but is also lighter on memory usage. Let's use quick sort for both follower count and influencer revenue sorting!

Complete the quick_sort and partition functions according to the given algorithms.

The process is started with quick_sort(A, 0, len(A)-1).

Complete quick_sort(nums, low, high):
1. If low is less than high:
  1. Partition the input list using the partition function and store the returned "middle" index
  2. Recursively call quick_sort on the left side of the partition
  3. Recursively call quick_sort on the right side of the partition
partition(nums, low, high):
1. Set pivot to the element at index high
2. Set i to the index before low
3. For each index (j) from low to high:
  1. If the element at index j is less than the pivot:
    1. Increment i by 1
    2. Swap the element at index i with the element at index j
4. Swap the element to the right of i with the element at index high (the pivot's position)
5. Return the new index of the pivot element (the item in the "middle" of the partition)