Quick Sort Algorithm in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Quick Sort algorithm?

Quick Sort picks a 'pivot' element and divides the list into two parts: elements smaller than the pivot and elements larger than the pivot. It then sorts these parts separately and combines them.

beginner

What role does the pivot play in Quick Sort?

The pivot is the element used to split the list into smaller and larger parts. It helps organize the list so that all smaller elements come before it and all larger elements come after it.

intermediate

Explain the partition step in Quick Sort.

Partition rearranges the list so that elements less than the pivot are on the left, and elements greater than the pivot are on the right. The pivot ends up in its correct sorted position.

intermediate

What is the average time complexity of Quick Sort?

The average time complexity of Quick Sort is O(n log n), where n is the number of elements. This means it sorts efficiently for most cases.

beginner

Why can Quick Sort be faster than other sorting algorithms like Bubble Sort?

Quick Sort uses divide and conquer to break the problem into smaller parts, sorting them quickly and combining results. Bubble Sort compares and swaps elements repeatedly, which is slower.

What does Quick Sort use to divide the list?

A A pivot element

B A temporary array

C A stack

D A queue

Quick Sort uses a pivot element to split the list into smaller and larger parts.

What happens to the pivot after partitioning?

A It stays in the same place

B It moves to its correct sorted position

C It swaps with the first element

D It is removed from the list

After partitioning, the pivot is placed where all smaller elements are left and larger elements are right, so it is in the correct position.

What is the worst-case time complexity of Quick Sort?

A O(n)

B O(n log n)

C O(n^2)

D O(log n)

In the worst case, Quick Sort can take O(n^2) time, for example when the smallest or largest element is always chosen as pivot.

Which technique does Quick Sort use?

A Divide and conquer

B Dynamic programming

C Greedy algorithm

D Backtracking

Quick Sort uses divide and conquer by splitting the list and sorting parts separately.

Which of these is NOT a step in Quick Sort?

A Recursively sorting sublists

B Partitioning the list

C Choosing a pivot

D Merging sorted lists

Quick Sort does not merge sorted lists; it sorts in place after partitioning.

Describe how Quick Sort sorts a list step-by-step.

Think about how the list is split and sorted in parts.

Explain why Quick Sort is efficient on average but can be slow in the worst case.

Consider how the pivot affects the splits.

Practice

1. What is the main idea behind the Quick Sort algorithm?

easy

A. Merge two sorted lists into one sorted list

B. Compare every element with every other element and swap if needed

C. Insert elements one by one into a sorted part of the list

D. Divide the list into smaller parts using a pivot and sort them recursively

Solution

1. Step 1: Understand Quick Sort's approach

   Quick Sort picks a pivot element and divides the list into parts smaller and larger than the pivot.

2. Step 2: Recursive sorting of parts

   It then sorts these parts by calling itself on each part, making the whole list sorted.

3. Final Answer:

   Divide the list into smaller parts using a pivot and sort them recursively -> Option D

4. Quick Check:

   Quick Sort = Divide and conquer with pivot [OK]

Hint: Remember: Quick Sort uses a pivot to split and sort recursively [OK]

Common Mistakes:

• Confusing Quick Sort with Bubble Sort or Merge Sort
• Thinking Quick Sort compares all pairs directly
• Believing Quick Sort merges sorted lists

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

easy

A. func quickSort(arr []int) []int

B. func quickSort(arr int[]) int[]

C. func quickSort(arr array of int) array of int

D. function quickSort(arr: []int) -> []int

Solution

1. Step 1: Check Go function syntax

   In Go, functions are declared with func, parameter types after names, and return types after parameters.

2. Step 2: Match correct parameter and return types

   arr []int means a slice of integers, and []int as return type means returning a slice of integers.

3. Final Answer:

   func quickSort(arr []int) []int -> Option A

4. Quick Check:

   Go func syntax = func name(params) returns [OK]

Hint: Go functions: func name(params type) returnType [OK]

Common Mistakes:

• Using array syntax like int[] which is not Go style
• Writing 'function' instead of 'func'
• Placing types before parameter names

3. What will be the output of the following Go code snippet using Quick Sort on the array [3, 6, 2, 7, 5]?

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

func quickSort(arr []int, low, high int) {
    if low < high {
        p := partition(arr, low, high)
        quickSort(arr, low, p-1)
        quickSort(arr, p+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
}

medium

A. [7 6 5 3 2]

B. [3 2 5 6 7]

C. [2 3 5 6 7]

D. [2 3 6 5 7]

Solution

1. Step 1: Understand partition and recursive calls

   The partition function picks the last element as pivot and rearranges elements smaller than pivot to the left. Recursive calls sort left and right parts.

2. Step 2: Trace sorting of [3,6,2,7,5]

   Pivot 5 moves elements less than 5 left: [3,2,5,7,6]. Then recursively sort [3,2] and [7,6]. Final sorted array is [2 3 5 6 7].

3. Final Answer:

   [2 3 5 6 7] -> Option C

4. Quick Check:

   Quick Sort output = sorted array ascending [OK]

Hint: Quick Sort output is sorted ascending array [OK]

Common Mistakes:

• Confusing pivot placement causing wrong order
• Not sorting both left and right parts recursively
• Mixing up indices in partition function

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

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

medium

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

B. Swap indices in last line should be arr[i+1], arr[low]

C. Loop should start from j = low, not low + 1

D. Return value should be low, not i

Solution

1. Step 1: Check pivot choice in partition

   Standard Quick Sort uses last element as pivot for partitioning, but here pivot is first element which changes logic.

2. Step 2: Understand impact of pivot choice

   Using arr[low] as pivot requires different partition logic; current swaps and indices assume pivot at end, causing incorrect partition.

3. Final Answer:

   Pivot should be arr[high], not arr[low] -> Option A

4. Quick Check:

   Pivot position must match partition logic [OK]

Hint: Pivot usually last element in standard Quick Sort partition [OK]

Common Mistakes:

• Changing pivot without adjusting partition logic
• Incorrect swap indices causing wrong array order
• Returning wrong partition index

5. You want to sort a large list of integers using Quick Sort but want to optimize for the worst-case scenario. Which modification helps reduce the chance of worst-case performance?

hard

A. Always pick the first element as pivot

B. Pick a random element as pivot each time

C. Sort the list first before applying Quick Sort

D. Use Bubble Sort instead for large lists

Solution

1. Step 1: Understand worst-case in Quick Sort

   Worst-case happens when pivot divides list unevenly, e.g., always smallest or largest element.

2. Step 2: Use random pivot to avoid worst-case

   Choosing a random pivot reduces chance of always bad splits, improving average performance.

3. Final Answer:

   Pick a random element as pivot each time -> Option B

4. Quick Check:

   Random pivot reduces worst-case risk [OK]

Hint: Random pivot choice avoids worst-case splits [OK]

Common Mistakes:

• Always picking first element causes worst-case on sorted input
• Sorting before Quick Sort wastes effort
• Using Bubble Sort is inefficient for large lists