Quick Sort Algorithm in DSA Python - Execution Trace

Concept Flow - Quick Sort Algorithm

Choose pivot element

↓

Partition array around pivot

↓

Left sub-array < pivot

↓

Recursively quicksort left

↓

Combine sorted parts

↓

Sorted array

Quick Sort picks a pivot, splits the array into smaller and bigger parts, sorts each part recursively, then combines them.

Execution Sample

DSA Python

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[-1]
    left = [x for x in arr[:-1] if x <= pivot]
    right = [x for x in arr[:-1] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

This code sorts an array by choosing the last element as pivot, partitioning, and recursively sorting parts.

Execution Table

Step	Operation	Array State	Pivot	Left Partition	Right Partition	Result After Step
1	Start with full array	[8, 3, 7, 6, 2]	N/A	N/A	N/A	[8, 3, 7, 6, 2]
2	Choose pivot	[8, 3, 7, 6, 2]	2	N/A	N/A	[8, 3, 7, 6, 2]
3	Partition around pivot	[8, 3, 7, 6, 2]	2	[]	[8, 3, 7, 6]	[2]
4	Recursively sort left partition	[]	N/A	N/A	N/A	[]
5	Recursively sort right partition	[8, 3, 7, 6]	N/A	N/A	N/A	[8, 3, 7, 6]
6	Choose pivot	[8, 3, 7, 6]	6	N/A	N/A	[8, 3, 7, 6]
7	Partition around pivot	[8, 3, 7, 6]	6	[3]	[8, 7]	[6]
8	Recursively sort left partition	[3]	N/A	N/A	N/A	[3]
9	Recursively sort right partition	[8, 7]	N/A	N/A	N/A	[8, 7]
10	Choose pivot	[8, 7]	7	N/A	N/A	[8, 7]
11	Partition around pivot	[8, 7]	7	[]	[8]	[7]
12	Recursively sort left partition	[]	N/A	N/A	N/A	[]
13	Recursively sort right partition	[8]	N/A	N/A	N/A	[8]
14	Combine sorted parts	N/A	N/A	N/A	N/A	[7, 8]
15	Combine sorted parts	N/A	N/A	N/A	N/A	[3, 6, 7, 8]
16	Combine sorted parts	N/A	N/A	N/A	N/A	[2, 3, 6, 7, 8]

💡 Recursion ends when sub-arrays have 0 or 1 element, which are already sorted.

Variable Tracker

Variable	Start	After Step 3	After Step 7	After Step 11	Final
arr	[8, 3, 7, 6, 2]	[8, 3, 7, 6, 2]	[8, 3, 7, 6]	[8, 7]	[2, 3, 6, 7, 8]
pivot	N/A	2	6	7	N/A
left	N/A	[]	[3]	[]	N/A
right	N/A	[8, 3, 7, 6]	[8, 7]	[8]	N/A
result	N/A	[2]	[6]	[7]	[2, 3, 6, 7, 8]

Key Moments - 3 Insights

Why do we choose the last element as pivot?

Choosing the last element as pivot is a simple rule to split the array; it helps us divide the array into smaller and bigger parts as shown in steps 2 and 6 in the execution_table.

Why does recursion stop when the array has 0 or 1 element?

Because an array with 0 or 1 element is already sorted, so no further sorting is needed. This is shown in steps 4, 8, 9, 12, and 13 where recursion returns immediately.

How do left and right partitions form during partitioning?

Left partition contains elements less than or equal to pivot, right partition contains elements greater than pivot. See step 3 and 7 where left and right arrays are created.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the left partition?

A []

B [8, 3, 7, 6]

C [2]

D [3]

💡 Hint

Check the 'Left Partition' column at step 3 in execution_table.

At which step does the pivot equal 6?

A Step 2

B Step 7

C Step 6

D Step 10

💡 Hint

Look at the 'Pivot' column in execution_table to find when pivot is 6.

If the pivot was chosen as the first element instead of last, how would step 2 change?

A Pivot would be 6 instead of 2

B Pivot would be 8 instead of 2

C Pivot would be 2 instead of 8

D Pivot would not change

💡 Hint

Step 2 shows pivot as last element; changing pivot to first element changes pivot value.

Concept Snapshot

Quick Sort Algorithm:
- Pick a pivot (commonly last element)
- Partition array into left (<= pivot) and right (> pivot)
- Recursively sort left and right partitions
- Combine sorted parts
- Stops when sub-array size ≤ 1 (already sorted)

Full Transcript

Quick Sort works by picking a pivot element from the array, usually the last element. It then splits the array into two parts: elements less than or equal to the pivot go to the left partition, and elements greater go to the right partition. Each partition is then sorted recursively using the same process. When the partitions have zero or one element, they are already sorted, so recursion stops. Finally, the sorted left partition, pivot, and sorted right partition are combined to form the sorted array. This process repeats until the entire array is sorted.

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