Quick Sort Algorithm in DSA Go - Time & Space Complexity

Time Complexity: Quick Sort Algorithm

O(n log n)

Understanding Time Complexity

We want to understand how the time to sort a list using Quick Sort changes as the list grows.

How does the number of steps grow when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code sorts an array by picking a pivot, splitting the array into parts, and sorting each part recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the array to split it around the pivot.
• How many times: This splitting happens at each recursive call, dividing the array into smaller parts.

How Execution Grows With Input

Each time we split, we do work proportional to the current size, and then repeat on smaller parts.

Input Size (n)	Approx. Operations
10	About 30 to 40 operations
100	About 700 to 800 operations
1000	About 10,000 to 15,000 operations

Pattern observation: The operations grow a bit faster than the input size but not as fast as the square of the input.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to sort grows a little more than linearly, multiplying the input size by its logarithm.

Common Mistake

[X] Wrong: "Quick Sort always takes the same time regardless of input order."

[OK] Correct: If the pivot choices are poor, Quick Sort can take much longer, up to O(n^2) in the worst case.

Interview Connect

Understanding Quick Sort's time complexity helps you explain why it is fast on average and what cases slow it down, showing your grasp of sorting algorithms.

Self-Check

"What if we always picked the first element as pivot instead of the middle? How would the time complexity change?"

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