Quick Sort as Divide and Conquer in DSA Python - Execution Trace

Concept Flow - Quick Sort as Divide and Conquer

Choose pivot element

↓

Partition array into two parts

↓

v < pivot

↓

Recursively apply Quick Sort on left part

↓

Recursively apply Quick Sort on right part

↓

Combine parts

↓

Sorted array

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

Execution Sample

DSA Python

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

This code sorts an array by choosing a middle pivot, splitting into smaller, equal, and bigger parts, then sorting parts recursively.

Execution Table

Step	Operation	Array State	Pivot	Partition Result	Recursive Calls
1	Start quick_sort	[3,8,10,6,1,2,1]	6	Left: [3,1,2,1], Middle: [6], Right: [8,10]	quick_sort([3,1,2,1]), quick_sort([8,10])
2	quick_sort left part	[3,1,2,1]	2	Left: [1,1], Middle: [2], Right: [3]	quick_sort([1,1]), quick_sort([3])
3	quick_sort left-left part	[1,1]	1	Left: [], Middle: [1,1], Right: []	quick_sort([]), quick_sort([])
4	quick_sort left-left-left part	[]	-	-	-
5	quick_sort left-left-right part	[]	-	-	-
6	Return sorted left-left part	[1,1]	-	-	-
7	quick_sort left-right part	[3]	-	-	-
8	Return sorted left-right part	[3]	-	-	-
9	Return sorted left part	[1,1,2,3]	-	-	-
10	quick_sort right part	[8,10]	10	Left: [8], Middle: [10], Right: []	quick_sort([8]), quick_sort([])
11	quick_sort right-left part	[8]	-	-	-
12	Return sorted right-left part	[8]	-	-	-
13	quick_sort right-right part	[]	-	-	-
14	Return sorted right-right part	[]	-	-	-
15	Return sorted right part	[8,10]	-	-	-
16	Combine all parts	[1,1,2,3,6,8,10]	-	-	-
17	End	[1,1,2,3,6,8,10]	-	-	-

💡 Recursion ends when sub-array length is 0 or 1, which are already sorted.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 9	After Step 10	After Step 15	Final
arr	[3,8,10,6,1,2,1]	[3,8,10,6,1,2,1]	[3,1,2,1]	[1,1]	[1,1,2,3]	[8,10]	[8,10]	[1,1,2,3,6,8,10]
pivot	-	6	2	1	-	10	-	-
left	-	[3,1,2,1]	[1,1]	[]	[1,1,2,3]	[8]	[8,10]	-
middle	-	[6]	[2]	[1,1]	-	[10]	[10]	-
right	-	[8,10]	[3]	[]	-	[]	[]	-

Key Moments - 3 Insights

Why does the recursion stop when the array length is 1 or 0?

Because arrays with 0 or 1 element are already sorted, so no further splitting or sorting is needed. See execution_table rows 4,5,11,13 where empty or single-element arrays return immediately.

Why do we pick the middle element as pivot?

Choosing the middle element helps balance the partitions on average, avoiding worst-case splits. In execution_table step 1, pivot is 6, which splits array into smaller and bigger parts.

How does the array get combined back after recursion?

After sorting left and right parts recursively, the function returns left + middle + right concatenated. See execution_table step 16 where all parts combine into the sorted array.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the pivot chosen for the left part?

A 6

B 2

C 1

D 3

💡 Hint

Check the 'Pivot' column at step 2 in execution_table.

At which step does the recursion return the sorted array [1,1]?

A Step 3

B Step 9

C Step 6

D Step 12

💡 Hint

Look for the step where the left-left part returns sorted [1,1] in execution_table.

If the pivot was chosen as the first element instead of the middle, how would the partition result at step 1 change?

A Left would include elements less than 3 instead of 6

B Right would include elements greater than 6 instead of 3

C Middle would be empty

D Partition would not change

💡 Hint

Compare partition logic in execution_table step 1 with pivot 6 vs pivot 3.

Concept Snapshot

Quick Sort picks a pivot element (usually middle).
It splits array into three parts: less than, equal to, and greater than pivot.
Recursively sorts left and right parts.
Combines sorted parts for final sorted array.
Stops recursion when sub-array size ≤ 1.

Full Transcript

Quick Sort is a sorting method that uses divide and conquer. It picks a pivot element from the array, then splits the array into three parts: elements less than the pivot, elements equal to the pivot, and elements greater than the pivot. It then sorts the left and right parts by calling itself recursively. When the sub-array has one or zero elements, it is already sorted, so the recursion stops. Finally, it combines the sorted left part, the middle part, and the sorted right part to get the fully sorted array. This process repeats until the entire array is sorted.

Practice

1. What is the main idea behind the Quick Sort algorithm in the divide and conquer approach?

easy

A. Divide the list into smaller parts, sort them, and combine results

B. Sort the list by comparing every element with every other element

C. Use extra space to merge sorted lists

D. Sort the list by repeatedly swapping adjacent elements

Solution

1. Step 1: Understand divide and conquer in Quick Sort

   Quick Sort divides the list into smaller parts based on a pivot, sorts each part, then combines them.

2. Step 2: Compare with other sorting ideas

   Unlike bubble sort or merge sort, Quick Sort uses partitioning without extra space for merging.

3. Final Answer:

   Divide the list into smaller parts, sort them, and combine results -> Option A

4. Quick Check:

   Divide and conquer = splitting and sorting parts [OK]

Hint: Quick Sort splits and sorts parts separately [OK]

Common Mistakes:

• Confusing Quick Sort with bubble sort
• Thinking Quick Sort always uses extra space
• Believing Quick Sort compares all pairs

2. Which of the following is the correct way to choose a pivot in a Quick Sort implementation in Python to avoid worst-case scenarios?

easy

A. pivot = arr[0]

B. pivot = arr[len(arr)]

C. pivot = arr[len(arr)//2]

D. pivot = arr[-len(arr)]

Solution

1. Step 1: Identify good pivot strategies

   Pivot choice affects performance; first or equivalent leads to worst case on sorted data.

2. Step 2: Check each option

   A and C (equivalent to first) bad for sorted input. B out of range error. D middle element helps balance partitions.

3. Final Answer:

   pivot = arr[len(arr)//2] -> Option C

4. Quick Check:

   Middle pivot avoids unbalanced partitions [OK]

Hint: Middle pivot balances better than first [OK]

Common Mistakes:

• Using arr[len(arr)] causes IndexError
• Picking first element for all cases
• Using unusual negative indexing

3. What will be the output of the following Python code using Quick Sort?

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)

print(quick_sort([3, 6, 2, 7, 5]))

medium

A. [3, 2, 6, 5, 7]

B. [2, 3, 5, 6, 7]

C. [7, 6, 5, 3, 2]

D. [2, 3, 6, 5, 7]

Solution

1. Step 1: Trace the partitioning

   Pivot is 3. less = [2], greater = [6,7,5]. Recursively sort less and greater.

2. Step 2: Recursively sort less and greater

   quick_sort([2]) returns [2]. quick_sort([6,7,5]) picks pivot 6, less=[5], greater=[7]. Sorting less and greater gives [5] and [7].

3. Step 3: Combine results

   quick_sort([6,7,5]) returns [5,6,7]. Final result is [2] + [3] + [5,6,7] = [2,3,5,6,7].

4. Final Answer:

   [2, 3, 5, 6, 7] -> Option B

5. Quick Check:

   Sorted list = [2, 3, 5, 6, 7] [OK]

Hint: Follow pivot splits and recursive calls carefully [OK]

Common Mistakes:

• Not including pivot in final list
• Mixing less and greater lists order
• Forgetting base case for recursion

4. Identify the error in this Quick Sort code snippet:

def quick_sort(arr):
    if len(arr) == 0:
        return arr
    pivot = arr[0]
    less = [x for x in arr if x < pivot]
    greater = [x for x in arr if x > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)

medium

A. Greater list should include elements equal to pivot

B. Pivot should be last element, not first

C. Less list includes pivot causing infinite recursion

D. Base case should be len(arr) <= 1, not == 0

Solution

1. Step 1: Check base case

   len(arr) == 0 handles empty lists fine; len(arr) <= 1 is more conventional but not required here.

2. Step 2: Analyze less and greater lists

   less takes x < pivot, greater x > pivot from entire arr. Pivot excluded correctly, but elements equal to pivot (duplicates) excluded from both.

3. Step 3: Identify the cause of incorrect output

   Duplicates equal to pivot are lost; should partition equals into less (<=) or greater (>=).

4. Final Answer:

   Greater list should include elements equal to pivot -> Option A

5. Quick Check:

   Strict < and > lose duplicates [OK]

Hint: Handle equals in one partition to avoid losing duplicates [OK]

Common Mistakes:

• Using wrong base case length
• Including pivot in less or greater lists
• Not handling equal elements properly

5. Given the list [4, 2, 5, 2, 3, 4], how many recursive calls will the following Quick Sort function make until fully sorted?

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)

quick_sort([4, 2, 5, 2, 3, 4])

hard

A. 6

B. 9

C. 5

D. 7

Solution

1. Step 1: Trace recursive calls

   Initial call with [4,2,5,2,3,4]. Pivot=4. less=[2,2,3,4], greater=[5].

2. Step 2: Recursive call on less=[2,2,3,4]

   Pivot=2. less=[2], greater=[3,4].

3. Step 3: Recursive call on less=[2]

   Length 1, base case, no rec calls.

4. Step 4: Recursive call on greater=[3,4]

   Pivot=3. less=[], greater=[4].

5. Step 5: Recursive calls on less=[] and greater=[4]

   Both base cases, no further rec calls.

6. Step 6: Recursive call on greater=[5]

   Base case.

7. Step 7: Count total recursive calls

   Counting all calls including base cases: initial call + quick_sort(less) + quick_sort(greater) + recursive calls inside less and greater partitions results in 7 total calls.

8. Final Answer:

   7 -> Option D

9. Quick Check:

   Count each function call including base cases [OK]

Hint: Count each function call including base cases [OK]

Common Mistakes:

• Ignoring base case calls
• Counting only partition steps
• Miscounting calls on empty lists