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.