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

Concept Flow - Quick Sort as Divide and Conquer

Choose pivot element

↓

Partition array into two parts

↓

v < pivot

↓

Recursively apply Quick Sort

↓

Combine results

↓

Sorted array

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

Execution Sample

DSA Go

func quickSort(arr []int) []int {
  if len(arr) <= 1 {
    return arr
  }
  pivot := arr[len(arr)/2]
  left, right := []int{}, []int{}
  for _, v := range arr {
    if v < pivot { left = append(left, v) } else if v > pivot { right = append(right, v) }
  }
  return append(append(quickSort(left), pivot), quickSort(right)...) 
}

This Go function sorts an array using Quick Sort by picking a middle pivot and recursively sorting left and right parts.

Execution Table

Step	Operation	Array State	Pivot	Left Part	Right Part	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]	7	N/A	N/A	[8, 3, 7, 6, 2]
3	Partition array	[8, 3, 7, 6, 2]	7	[3, 6, 2]	[8]	Pivot 7 separated
4	Recursively sort left part	[3, 6, 2]	6	[3, 2]	[]	Sorting left part
5	Partition left part	[3, 6, 2]	6	[3, 2]	[]	Left part partitioned
6	Recursively sort left-left part	[3, 2]	2	[]	[3]	Sorting left-left part
7	Partition left-left part	[3, 2]	2	[]	[3]	Left-left part partitioned
8	Recursively sort left-left-left part	[]	N/A	[]	[]	Empty, return []
9	Recursively sort left-left-right part	[3]	N/A	[]	[]	Single element, return [3]
10	Combine left-left parts	N/A	2	[]	[3]	[2, 3]
11	Recursively sort left-right part	[]	N/A	[]	[]	Empty, return []
12	Combine left parts	N/A	6	[2, 3]	[]	[2, 3, 6]
13	Recursively sort right part	[8]	N/A	[]	[]	Single element, return [8]
14	Combine all parts	N/A	7	[2, 3, 6]	[8]	[2, 3, 6, 7, 8]
15	Sorting complete	[2, 3, 6, 7, 8]	N/A	N/A	N/A	[2, 3, 6, 7, 8]

💡 All parts reduced to single elements or empty, combined to form sorted array.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 10	After Step 12	After Step 14	Final
arr	[8, 3, 7, 6, 2]	[8, 3, 7, 6, 2]	[3, 6, 2]	[3, 2]	[2, 3]	[2, 3, 6]	[2, 3, 6, 7, 8]	[2, 3, 6, 7, 8]
pivot	N/A	7	6	2	2	6	7	N/A
left	N/A	[3, 6, 2]	[3, 2]	[]	[]	[2, 3]	[2, 3, 6]	N/A
right	N/A	[8]	[]	[3]	[3]	[]	[8]	N/A

Key Moments - 3 Insights

Why do we exclude the pivot element from left and right parts during partition?

Because the pivot is placed between left and right parts after sorting them, as seen in steps 3 and 14 in the execution_table.

What happens when the array has only one element or is empty?

The function returns the array immediately without further recursion, shown in steps 8, 9, and 13 where single or empty arrays return as is.

Why do we pick the middle element as pivot?

Choosing the middle element helps balance partitions on average, reducing worst-case scenarios, as shown in step 2 where pivot is 7 (middle of array).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what are the left and right parts after partition?

A Left: [8, 3, 7], Right: [6, 2]

B Left: [3, 2], Right: [6, 8]

C Left: [3, 6, 2], Right: [8]

D Left: [2, 3, 6], Right: [7, 8]

💡 Hint

Check the 'Left Part' and 'Right Part' columns in execution_table row for step 3.

At which step does the recursion stop because the array has only one element?

A Step 5

B Step 9

C Step 12

D Step 3

💡 Hint

Look for steps where 'Result after Step' shows a single element array.

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

A Pivot would be 8, left: [3, 7, 6, 2], right: []

B Pivot would be 8, left: [3, 7, 6, 2], right: [7]

C Pivot would be 3, left: [2], right: [8, 7, 6]

D Pivot would be 2, left: [], right: [8, 3, 7, 6]

💡 Hint

If pivot is first element 8, all smaller go left, none bigger go right, check execution_table step 3 for comparison.

Concept Snapshot

Quick Sort divides array by pivot
Partitions into smaller and bigger parts
Recursively sorts parts
Combines sorted parts with pivot
Efficient average O(n log n) sorting

Full Transcript

Quick Sort works by picking a pivot element from the array, usually the middle one. It then splits the array into two parts: elements smaller than the pivot go to the left, and elements bigger go to the right. The pivot itself is kept separate. Then, Quick Sort is called again on the left and right parts, sorting them recursively. When the parts are small enough (one or zero elements), they are returned as is. Finally, the sorted left part, pivot, and sorted right part are combined to form the fully sorted array. This divide and conquer approach efficiently sorts arrays on average in O(n log n) time.

Practice

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

easy

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

B. Sort the array by repeatedly swapping adjacent elements

C. Use extra memory to merge two sorted arrays

D. Sort the array by selecting the smallest element each time

Solution

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

   Quick Sort divides the array into parts around a pivot, sorts parts recursively.

2. Step 2: Compare with other sorting methods

   Unlike bubble or selection sort, Quick Sort uses division and conquering subproblems.

3. Final Answer:

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

4. Quick Check:

   Divide and conquer = divide, sort, combine [OK]

Hint: Remember: divide, sort parts, then combine [OK]

Common Mistakes:

• Confusing Quick Sort with bubble or selection sort
• Thinking Quick Sort merges arrays like merge sort
• Ignoring the pivot selection step

2. Which of the following is the correct way to declare a partition function header in Go for Quick Sort?

easy

A. func partition(arr []int, low int, high int) int

B. func partition(arr int[], low int, high int) int

C. func partition(arr []int, low, high int) string

D. func partition(arr []int, low int, high int)

Solution

1. Step 1: Check Go syntax for function parameters

   In Go, slices are declared as []int, and multiple parameters can be declared with types.

2. Step 2: Verify return type for partition

   Partition returns an int index, so return type must be int.

3. Final Answer:

   func partition(arr []int, low int, high int) int -> Option A

4. Quick Check:

   Go func syntax with slice and int return = func partition(arr []int, low int, high int) int [OK]

Hint: Go slices use []type, return type must match function purpose [OK]

Common Mistakes:

• Using incorrect array syntax like int[]
• Wrong return type for partition function
• Missing return type in function declaration

3. What will be the output of the following Go code snippet after calling quickSort(arr, 0, len(arr)-1)?

func partition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low - 1
    for j := low; j < high; j++ {
        if arr[j] < pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

func quickSort(arr []int, low, high int) {
    if low < high {
        pi := partition(arr, low, high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
    }
}

func main() {
    arr := []int{4, 2, 7, 1}
    quickSort(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

medium

A. [7 4 2 1]

B. [4 2 7 1]

C. [1 2 4 7]

D. [1 4 2 7]

Solution

1. Step 1: Trace partition and quickSort on array [4, 2, 7, 1]

   Pivot is last element; after partition, smaller elements move left; recursive calls sort subarrays.

2. Step 2: Final sorted array after all recursive calls

   Array becomes [1, 2, 4, 7] after full quick sort completes.

3. Final Answer:

   [1 2 4 7] -> Option C

4. Quick Check:

   Quick Sort sorts array ascending = [1 2 4 7] [OK]

Hint: Quick Sort sorts in place; final array is sorted ascending [OK]

Common Mistakes:

• Assuming array stays unchanged
• Confusing pivot placement
• Ignoring recursive calls

4. Identify the bug in this Go Quick Sort partition function:

func partition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low
    for j := low; j < high; j++ {
        if arr[j] < pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

medium

A. Pivot should be arr[high], not arr[low]

B. Loop should start from low, not low + 1

C. Swap after loop should be arr[high], arr[i]

D. Variable i should be initialized to low - 1

Solution

1. Step 1: Analyze initialization of i in partition

   In standard Lomuto partition with pivot at arr[high], i should start at low - 1 to track smaller elements correctly.

2. Step 2: Check loop and swap logic

   Loop and swaps are correct if i starts at low - 1; current i = low causes incorrect partitioning.

3. Final Answer:

   Variable i should be initialized to low - 1 -> Option D

4. Quick Check:

   Correct i start fixes partition logic [OK]

Hint: Initialize i = low - 1 for Lomuto partition with pivot at end [OK]

Common Mistakes:

• Starting i at low causes wrong partition index
• Confusing pivot position with swap indices
• Changing pivot without adjusting i initialization

5. Given an array with many duplicate elements, which modification to Quick Sort helps improve performance and avoid worst-case behavior?

hard

A. Always choose the first element as pivot

B. Use a three-way partitioning to separate less, equal, and greater elements

C. Avoid recursion by using a single loop

D. Sort only the first half of the array

Solution

1. Step 1: Understand problem with duplicates in Quick Sort

   Duplicates cause many equal elements, leading to unbalanced partitions and slow sorting.

2. Step 2: Apply three-way partitioning solution

   Three-way partitioning divides array into less than, equal to, and greater than pivot, improving efficiency.

3. Final Answer:

   Use a three-way partitioning to separate less, equal, and greater elements -> Option B

4. Quick Check:

   Three-way partitioning handles duplicates better [OK]

Hint: Three-way partitioning handles duplicates efficiently [OK]

Common Mistakes:

• Choosing fixed pivot causes worst-case on duplicates
• Trying to avoid recursion breaks divide and conquer
• Sorting only half misses elements