Quick Sort Algorithm in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Quick Sort Partition Step

What is the output of the array after the partition step in Quick Sort using the last element as pivot?

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{10, 7, 8, 9, 1, 5}
pi := partition(arr, 0, len(arr)-1)
fmt.Println(arr)

A [1 5 7 8 9 5]

B [1 5 7 9 8 10]

C [1 5 7 8 9 10]

D [10 7 8 9 1 5]

💡 Hint

Focus on how elements smaller than the pivot are moved before it.

The partition function moves all elements smaller than the pivot (last element) to the left and places the pivot after them. The array after partitioning is [1 5 7 8 9 10].

🧠 Conceptual

intermediate

Quick Sort Average Time Complexity

What is the average time complexity of the Quick Sort algorithm?

A O(n^2)

B O(n log n)

C O(log n)

D O(n)

💡 Hint

Think about how the array is divided and conquered.

Quick Sort on average divides the array into two halves and sorts recursively, leading to O(n log n) time complexity.

❓ Predict Output

advanced

Final Sorted Array After Quick Sort

What is the final sorted array after applying Quick Sort on the given array?

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

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, 6, 9, 3}
quickSort(arr, 0, len(arr)-1)
fmt.Println(arr)

A [2 3 4 6 9]

B [4 2 3 6 9]

C [9 6 4 3 2]

D [2 4 3 6 9]

💡 Hint

Quick Sort sorts the array in ascending order.

Quick Sort sorts the array fully in ascending order, so the final output is [2 3 4 6 9].

🔧 Debug

advanced

Identify the Bug in Quick Sort Partition

What error will this Quick Sort partition code cause when run?

DSA Go

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

A Incorrect partition index causing wrong sort

B Index out of range error

C Infinite loop

D No error, works correctly

💡 Hint

Check how the initial value of i affects the partitioning.

The initial value of i should be low - 1, not low. Starting at low causes incorrect partition index and wrong sorting.

🚀 Application

expert

Quick Sort Stability Check

Given the array of structs [{value: 3, id: 'a'}, {value: 3, id: 'b'}, {value: 1, id: 'c'}], which statement about Quick Sort is true?

A Quick Sort is stable and keeps the order of equal elements

B Quick Sort cannot sort structs

C Quick Sort always sorts in descending order

D Quick Sort is unstable and may change the order of equal elements

💡 Hint

Think about how Quick Sort swaps elements during partition.

Quick Sort is not stable because it swaps elements that may change the relative order of equal elements.