Quick Sort as Divide and Conquer in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Quick Sort Partition Step

What is the output of the partition function after running on the array [4, 2, 7, 1, 3] with pivot as the last element?

DSA Go

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
}

arr := []int{4, 2, 7, 1, 3}
pos := partition(arr, 0, len(arr)-1)
fmt.Println(arr, pos)

A [1 2 3 4 7] 2

B [2 1 3 7 4] 3

C [2 1 3 4 7] 2

D [1 2 3 7 4] 2

💡 Hint

Remember the pivot is the last element, and elements less than pivot move to the left.

The partition function moves all elements less than pivot (3) to the left and places pivot after them. The final array is [2, 1, 3, 4, 7] with pivot index 2.

🧠 Conceptual

intermediate

Understanding Quick Sort Recursive Calls

In Quick Sort, after partitioning the array, which parts are sorted recursively?

A Only the left sub-array before the pivot

B Both left and right sub-arrays excluding the pivot

C Only the right sub-array after the pivot

D The entire array again including the pivot

💡 Hint

Think about where the pivot ends up after partitioning.

After partitioning, the pivot is in its correct position. Quick Sort recursively sorts the left and right sub-arrays excluding the pivot.

🔧 Debug

advanced

Identify the Bug in Quick Sort Partition

What error does this partition function cause when run on array [5, 3, 8, 4, 2]? func partition(arr []int, low, high int) int { pivot := arr[low] i := low + 1 for j := low + 1; j <= high; j++ { if arr[j] < pivot { arr[i], arr[j] = arr[j], arr[i] i++ } } arr[low], arr[i-1] = arr[i-1], arr[low] return i - 1 }

DSA Go

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

arr := []int{5, 3, 8, 4, 2}
pos := partition(arr, 0, len(arr)-1)
fmt.Println(arr, pos)

A Index out of range error

B Wrong pivot position causing incorrect sort

C Infinite loop error

D No error, output: [2 3 4 5 8] 3

💡 Hint

Check how pivot is chosen and swapped.

No error. The partition function correctly rearranges the array to [2, 3, 4, 5, 8] with pivot at index 3.

📝 Syntax

advanced

Syntax Error in Quick Sort Implementation

Which option contains a syntax error in this Quick Sort snippet?

DSA Go

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)
    }
}

A

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)
    }

B

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)
    }
};

C

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)
    }
}}

D

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)
    }
}

💡 Hint

Check for missing closing braces.

Option A is missing the closing brace for the function, causing a syntax error.

🚀 Application

expert

Quick Sort Performance on Nearly Sorted Array

What is the time complexity of Quick Sort on a nearly sorted array if the pivot is always chosen as the first element?

A O(n^2) worst case

B O(n log n) average case

C O(n) best case

D O(log n) average case

💡 Hint

Consider how pivot choice affects partitioning on sorted data.

Choosing the first element as pivot on nearly sorted arrays causes unbalanced partitions, leading to worst-case O(n^2) time complexity.

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