Quick Sort Algorithm in DSA Go

Mental Model

Quick Sort splits the list into smaller parts around a pivot, sorting each part separately until the whole list is sorted.

Analogy: Imagine sorting a pile of cards by picking one card as a divider, then putting smaller cards on one side and bigger cards on the other, and repeating this for each side until all cards are in order.

Array: [7, 2, 9, 4, 3]
Pivot chosen: 3
Partitioned: [2] [3] [7, 9, 4]

Dry Run Walkthrough

Input: list: [7, 2, 9, 4, 3]

Goal: Sort the list in ascending order using Quick Sort

Step 1: Choose pivot as last element 3, partition array around pivot

[2, 3, 9, 4, 7]

Why: We move elements smaller than pivot to the left, bigger to the right

Step 2: Recursively quick sort left part [2]

[2]

Why: Single element is already sorted

Step 3: Recursively quick sort right part [9, 4, 7]

[4, 7, 9]

Why: Repeat partition and sort on right side

Step 4: Combine sorted parts: left [2], pivot [3], right [4, 7, 9]

[2, 3, 4, 7, 9]

Why: All parts sorted and combined form the sorted array

Result:

[2, 3, 4, 7, 9]

Annotated Code

DSA Go

package main

import "fmt"

func quickSort(arr []int, low, high int) {
    if low < high {
        pi := partition(arr, low, high) // partition array and get pivot index
        quickSort(arr, low, pi-1)       // sort left part
        quickSort(arr, pi+1, high)      // sort right part
    }
}

func partition(arr []int, low, high int) int {
    pivot := arr[high]                 // choose pivot as last element
    i := low - 1                      // index of smaller element
    for j := low; j < high; j++ {
        if arr[j] <= pivot {           // if current element smaller or equal to pivot
            i++                       // move smaller element index forward
            arr[i], arr[j] = arr[j], arr[i] // swap smaller element to front
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1] // place pivot after smaller elements
    return i + 1                     // return pivot index
}

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

pi := partition(arr, low, high) // partition array and get pivot index

partition array around pivot to separate smaller and bigger elements

quickSort(arr, low, pi-1) // sort left part

recursively sort left sub-array before pivot

quickSort(arr, pi+1, high) // sort right part

recursively sort right sub-array after pivot

if arr[j] <= pivot { // if current element smaller or equal to pivot

check if element should go to left side of pivot

arr[i], arr[j] = arr[j], arr[i] // swap smaller element to front

move smaller element to correct position

arr[i+1], arr[high] = arr[high], arr[i+1] // place pivot after smaller elements

put pivot in its correct sorted position

Output

[2 3 4 7 9]

Complexity Analysis

Time: O(n log n) average case because the list is divided roughly in half each time and each element is compared once per level

Space: O(log n) due to recursive call stack depth in average case

vs Alternative: Better than simple sorting like bubble sort O(n^2) because it divides and conquers instead of comparing all pairs

Edge Cases

empty array

function returns immediately without changes

DSA Go

if low < high {

array with one element

function returns immediately as single element is sorted

DSA Go

if low < high {

array with all equal elements

partition keeps elements in place, recursion ends quickly

DSA Go

if arr[j] <= pivot {

When to Use This Pattern

When you see a problem asking to sort or order elements efficiently, especially with large data, reach for Quick Sort because it sorts by dividing the list around pivots quickly.

Common Mistakes

Mistake: Choosing pivot incorrectly or not swapping pivot to correct position
Fix: Always swap pivot to its correct place after partitioning to ensure correct division

Mistake: Not handling base case low >= high causing infinite recursion
Fix: Add condition to stop recursion when sub-array size is 0 or 1

Summary

Quick Sort sorts an array by dividing it around a pivot and sorting each part recursively.

Use Quick Sort when you need an efficient, general-purpose sorting algorithm.

The key insight is partitioning the array so smaller elements go left and bigger go right around the pivot.

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