Quick Sort Algorithm in DSA Go - Build from Scratch

Quick Sort Algorithm

📖 Scenario: You have a list of numbers that you want to sort quickly so you can find the smallest or largest easily. Quick Sort is a fast way to do this by dividing the list into smaller parts and sorting those parts.

🎯 Goal: Build a Go program that sorts a list of numbers using the Quick Sort algorithm step-by-step.

📋 What You'll Learn

Create a slice of integers with exact values

Define a pivot index variable

Implement the partition step of Quick Sort

Print the sorted slice after applying Quick Sort

💡 Why This Matters

🌍 Real World

Quick Sort is used in many software systems to sort data quickly, such as sorting names, scores, or any list of items.

💼 Career

Understanding Quick Sort helps in coding interviews and building efficient software that handles large data sets.

1

Create the initial slice of numbers

Create a slice called numbers with these exact integers: 33, 10, 55, 71, 29, 3, 18

DSA Go

# Create the slice numbers with the given integers
# Your code here

Hint

Use numbers := []int{33, 10, 55, 71, 29, 3, 18} to create the slice.

2

Set the pivot index for partitioning

Add a variable called pivotIndex and set it to len(numbers) - 1 to use the last element as pivot

DSA Go

package main

func main() {
    numbers := []int{33, 10, 55, 71, 29, 3, 18}
    // Set pivotIndex to last element index
    // Your code here
}

Hint

Use pivotIndex := len(numbers) - 1 to get the last index.

3

Implement the partition step of Quick Sort

Write a function called partition that takes a slice of integers and a pivot index, and returns the new pivot position after rearranging elements smaller than pivot to the left and larger to the right. Then call partition(numbers, pivotIndex) inside main.

DSA Go

package main

func partition(arr []int, pivot int) int {
    // Your code here
}

func main() {
    numbers := []int{33, 10, 55, 71, 29, 3, 18}
    pivotIndex := len(numbers) - 1
    // Call partition function
    // Your code here
}

Hint

Use a loop to compare each element with the pivot value and swap smaller elements to the front.

4

Print the slice after partitioning

Add import "fmt" at the top and print the numbers slice after calling partition using fmt.Println(numbers)

DSA Go

package main

import "fmt"

func partition(arr []int, pivot int) int {
    pivotValue := arr[pivot]
    storeIndex := 0
    for i := 0; i < pivot; i++ {
        if arr[i] < pivotValue {
            arr[i], arr[storeIndex] = arr[storeIndex], arr[i]
            storeIndex++
        }
    }
    arr[storeIndex], arr[pivot] = arr[pivot], arr[storeIndex]
    return storeIndex
}

func main() {
    numbers := []int{33, 10, 55, 71, 29, 3, 18}
    pivotIndex := len(numbers) - 1
    partition(numbers, pivotIndex)
    // Print the numbers slice
    // Your code here
}

Hint

Use fmt.Println(numbers) to print the slice after partitioning.

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