Quick Sort Algorithm in DSA Python

Mental Model

Quick Sort splits the list into smaller parts around a pivot, sorting each part separately until the whole list is sorted.

Analogy: Imagine sorting a pile of cards by picking one card as a divider, putting smaller cards on one side and bigger cards on the other, then repeating this for each side until all cards are in order.

List: [7, 2, 5, 3, 9]
Pivot chosen: 9
Partitioned: [7, 2, 5, 3] -> 9 -> []

Dry Run Walkthrough

Input: list: [7, 2, 5, 3, 9]

Goal: Sort the list in ascending order using Quick Sort

Step 1: Choose pivot as last element 9, partition list into smaller and larger

[7, 2, 5, 3] -> 9

Why: We separate elements smaller than pivot to the left, larger to the right

Step 2: Recursively quick sort left part [7, 2, 5, 3]

Pivot 3 chosen, partition into [2] -> 3 -> [5, 7]

Why: Sort left part by choosing new pivot and partitioning

Step 3: Recursively quick sort right part [5, 7]

Pivot 7 chosen, partition into [5] -> 7 -> []

Why: Sort right part similarly

Step 4: Combine sorted parts: [2, 3, 5, 7, 9]

[2, 3, 5, 7, 9]

Why: All parts sorted and combined form the fully sorted list

Result:

[2, 3, 5, 7, 9]

Annotated Code

DSA Python

def quick_sort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)  # partition around pivot
        quick_sort(arr, low, pivot_index - 1)   # sort left part
        quick_sort(arr, pivot_index + 1, high)  # sort right part

def partition(arr, low, high):
    pivot = arr[high]  # choose last element as pivot
    i = low - 1  # index of smaller element
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # swap smaller element to front
    arr[i + 1], arr[high] = arr[high], arr[i + 1]  # place pivot in correct position
    return i + 1

# Driver code
arr = [7, 2, 5, 3, 9]
quick_sort(arr, 0, len(arr) - 1)
print(arr)

if low < high:

check if current segment has more than one element to sort

pivot_index = partition(arr, low, high) # partition around pivot

divide array into parts smaller and larger than pivot

quick_sort(arr, low, pivot_index - 1) # sort left part

recursively sort left sub-array

quick_sort(arr, pivot_index + 1, high) # sort right part

recursively sort right sub-array

pivot = arr[high] # choose last element as pivot

select pivot element for partitioning

for j in range(low, high):

iterate over elements to compare with pivot

if arr[j] <= pivot:

check if current element is smaller or equal to pivot

arr[i], arr[j] = arr[j], arr[i] # swap smaller element to front

move smaller element to left side

arr[i + 1], arr[high] = arr[high], arr[i + 1] # place pivot in correct position

put pivot between smaller and larger elements

Output

[2, 3, 5, 7, 9]

Complexity Analysis

Time: O(n log n) average case because the list is divided roughly in half each time and all elements are processed during partitioning

Space: O(log n) due to recursive call stack in average case

vs Alternative: Compared to bubble sort's O(n^2), Quick Sort is much faster on average due to divide and conquer approach

Edge Cases

empty list

function returns immediately without changes

DSA Python

if low < high:

list with one element

function returns immediately as no sorting needed

DSA Python

if low < high:

list with all elements equal

partitioning still works, but recursion depth may increase

DSA Python

if arr[j] <= pivot:

When to Use This Pattern

When you need to sort a list efficiently and can divide the problem into smaller parts, use Quick Sort because it sorts by splitting around a pivot.

Common Mistakes

Mistake: Choosing pivot incorrectly or not swapping elements properly during partition
Fix: Always pick a pivot (commonly last element) and swap elements smaller than pivot to the front before placing pivot in correct position

Summary

Quick Sort sorts a list by dividing it around a pivot and sorting each part recursively.

Use Quick Sort when you want an efficient, divide-and-conquer sorting method.

The key insight is partitioning the list so smaller elements go left and larger go right around the pivot.

Practice

1. What is the main idea behind the Quick Sort algorithm?

easy

A. Sort the list by inserting elements into their correct position one by one

B. Sort the list by repeatedly swapping adjacent elements

C. Divide the list into smaller parts using a pivot and sort them recursively

D. Sort the list by merging two sorted halves

Solution

1. Step 1: Understand Quick Sort approach

   Quick Sort picks a pivot element and divides the list into parts smaller and larger than the pivot.

2. Step 2: Recursive sorting

   It then sorts these parts recursively, combining them to get the sorted list.

3. Final Answer:

   Divide the list into smaller parts using a pivot and sort them recursively -> Option C

4. Quick Check:

   Quick Sort = Divide and conquer [OK]

Hint: Remember: pivot divides list, then sort parts recursively [OK]

Common Mistakes:

• Confusing Quick Sort with Bubble Sort
• Thinking Quick Sort merges sorted halves
• Assuming Quick Sort inserts elements one by one

2. Which of the following is the correct way to define the partition function header in Python for Quick Sort?

easy

A. def partition(arr, low, high):

B. def partition(arr):

C. def partition(low, high):

D. def partition(arr, pivot):

Solution

1. Step 1: Identify required parameters

   The partition function needs the array and the current low and high indices to work on a sublist.

2. Step 2: Match function signature

   Only def partition(arr, low, high): correctly includes all three parameters: arr, low, and high.

3. Final Answer:

   def partition(arr, low, high): -> Option A

4. Quick Check:

   Partition needs array and index bounds [OK]

Hint: Partition needs array plus low and high indexes [OK]

Common Mistakes:

• Omitting low and high parameters
• Using pivot as parameter instead of indices
• Defining partition with only one parameter

3. What will be the output of the following code snippet?

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr, 0, len(arr) - 1)
print(arr)

medium

A. [1, 1, 2, 3, 6, 8, 10]

B. [10, 8, 6, 3, 2, 1, 1]

C. [3, 6, 8, 10, 1, 2, 1]

D. [1, 2, 1, 3, 6, 8, 10]

Solution

1. Step 1: Understand partition and recursive calls

   The partition function places the pivot in correct position and divides array into smaller and larger parts. Quick sort recursively sorts these parts.

2. Step 2: Trace sorting of given array

   Starting with [3,6,8,10,1,2,1], after full recursion, the array becomes sorted ascending: [1,1,2,3,6,8,10].

3. Final Answer:

   [1, 1, 2, 3, 6, 8, 10] -> Option A

4. Quick Check:

   Quick Sort output = sorted array ascending [OK]

Hint: Quick Sort outputs sorted array ascending by default [OK]

Common Mistakes:

• Thinking Quick Sort sorts descending by default
• Confusing original array with sorted output
• Ignoring pivot placement effect

4. Identify the error in this Quick Sort partition function:

def partition(arr, low, high):
    pivot = arr[low]
    i = low + 1
    for j in range(low + 1, high):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[low], arr[i-1] = arr[i-1], arr[low]
    return i-1

medium

A. Swapping inside the loop is incorrect

B. Pivot should be arr[high] instead of arr[low]

C. Return statement should return 'i' instead of 'i-1'

D. The for loop should include 'high' index by using range(low + 1, high + 1)

Solution

1. Step 1: Check loop range for partitioning

   The for loop uses range(low + 1, high), which excludes the 'high' index element. It should include 'high' to consider the pivot's correct position.

2. Step 2: Correct loop range

   Changing to range(low + 1, high + 1) includes the last element, ensuring all elements are compared to pivot.

3. Final Answer:

   The for loop should include 'high' index by using range(low + 1, high + 1) -> Option D

4. Quick Check:

   Loop must cover full sublist including high index [OK]

Hint: Loop must include high index to compare all elements [OK]

Common Mistakes:

• Forgetting to include last element in loop
• Changing pivot position unnecessarily
• Returning wrong index after partition

5. You want to sort a list of strings by their length using Quick Sort. Which modification to the partition function is correct?

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if ???:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

What should replace ??? to sort by string length?

hard

A. arr[j].startswith(pivot)

B. len(arr[j]) <= len(pivot)

C. len(arr[j]) >= len(pivot)

D. arr[j] <= pivot

Solution

1. Step 1: Understand sorting by string length

   To sort strings by length, compare lengths of elements, not the strings themselves.

2. Step 2: Replace condition with length comparison

   Using len(arr[j]) <= len(pivot) ensures elements with length less or equal to pivot's length go left.

3. Final Answer:

   len(arr[j]) <= len(pivot) -> Option B

4. Quick Check:

   Compare lengths to sort strings by length [OK]

Hint: Compare lengths, not strings, to sort by length [OK]

Common Mistakes:

• Comparing strings lexicographically instead of length
• Using >= instead of <= causing reverse order
• Using unrelated string methods like startswith