Sorting Algorithms in Go

Lesson 5

Lesson Overview

Welcome to the lesson dedicated to Quick Sort in Go. Sorting is a fundamental class of algorithms in computer science. Understanding different methods of sorting becomes more crucial as data sizes increase.

Quick Look at QuickSort

The QuickSort algorithm is designed to sort an unsorted slice by employing the Divide and Conquer Technique. The algorithm efficiently achieves this with an average time complexity of O(n log n). The idea behind it is to pick a pivot element from the slice and partition the other elements into two slices according to whether they are less than or greater than the pivot.

Here's an overview of how QuickSort works in Go:

Pivot Selection: Choose a pivot element from the slice.
- The pivot can be any element, but commonly used strategies include picking the last element or selecting a random element.
Partitioning the Slice: Rearrange the slice such that:
- All elements less than the pivot come before the pivot.
- All elements greater than the pivot come after the pivot.
- The pivot element is now in its correct sorted position.
Recursive Sorting:
- Recursively apply the quickSort function to the sub-slice of elements with values less than the pivot.
- Recursively apply the quickSort function to the sub-slice of elements with values greater than the pivot.

Example:

Given the slice [10, 7, 8, 9, 1, 5], let's sort it using QuickSort:

Choose Pivot: Let's pick the last element, 5, as the pivot.
Partition:
- Elements less than 5: [1]
- Elements greater than 5: [10, 7, 8, 9]
- Slice after partitioning: [1, **5**, 10, 7, 8, 9]
Recursive QuickSort:
- Apply QuickSort to [1] (Already sorted)
- Apply QuickSort to [10, 7, 8, 9]
Repeat the process for the sub-slice [10, 7, 8, 9], choosing pivots, partitioning, and recursing until the entire slice is sorted.

This approach ensures that the sorting process is performed efficiently by continually breaking down the problem into smaller subproblems, which are easier to solve.

We will use a helper function: partition.

Implementation of QuickSort in Go

Go
1package main
2
3import (
4    "fmt"
5)
6
7// Partition function that makes use of pivot
8func partition(arr []int, low, high int) int {
9    pivot := arr[high] // pivot
10    i := low - 1       // Index of smaller element
11
12    for j := low; j < high; j++ {
13        // If the current element is smaller than or equal to the pivot
14        if arr[j] <= pivot {
15            i++
16            arr[i], arr[j] = arr[j], arr[i]
17        }
18    }
19    arr[i+1], arr[high] = arr[high], arr[i+1]
20    return i + 1
21}
22
23// The main function that implements QuickSort
24func quickSort(arr []int, low, high int) {
25    if low < high {
26        // pi is the partitioning index, arr[pi] is now at the right place
27        pi := partition(arr, low, high)
28        // Separately sort elements before partition and after partition
29        quickSort(arr, low, pi-1)
30        quickSort(arr, pi+1, high)
31    }
32}
33
34func main() {
35    arr := []int{10, 7, 8, 9, 1, 5}
36    n := len(arr)
37    quickSort(arr, 0, n-1)
38    fmt.Printf("Sorted array: %v\n", arr)  // Sorted array: [1, 5, 7, 8, 9, 10]
39}

Partition Breakdown

Let's break down the partition function step by step:

Function Definition

This line defines the partition function, which returns an integer. The function takes a slice of integers arr and two integers low and high as its parameters. These specify the sub-slice to be partitioned.

Go
1func partition(arr []int, low, high int) int

Initialize the Pivot

Select the last element in the sub-slice (indexed by high) as the pivot. The pivot is the reference value around which the slice will be partitioned.

Go
1pivot := arr[high] // pivot

Initialize the Partition Index

Initialize i to low - 1. This index keeps track of the boundary between elements smaller than the pivot and not yet positioned elements.

Go
1i := low - 1 // Index of smaller element

Iterate Over the Sub-slice

Use a for loop to iterate over the sub-slice from the low index to high - 1. This loop will compare each element with the pivot.

Go
1for j := low; j < high; j++

Compare Current Element with Pivot

Inside the loop, check if the current element arr[j] is less than or equal to the pivot.

Go
1if arr[j] <= pivot

Swap Elements if Condition is Met

If the current element arr[j] is less than or equal to the pivot:

Increment i.
Swap the elements at index i and j to move the smaller element to the correct side of the pivot.

Go
1i++
2arr[i], arr[j] = arr[j], arr[i]

Place Pivot in Correct Position

After the loop completes, place the pivot element in its correct sorted position by swapping it with the element at i + 1. This guarantees that all elements to the left of the pivot are smaller, and all elements to the right are larger.

Go
1arr[i+1], arr[high] = arr[high], arr[i+1]

Return the Partition Index

Return the partition index, which is i + 1. This index marks the final position of the pivot element.

Go
1return i + 1

In summary, the partition function rearranges the elements of the slice such that elements smaller than the pivot are on the left, and elements greater than the pivot are on the right. The pivot element is placed in its correct sorted position, and the function returns this index, effectively dividing the slice into two sub-slices around the pivot for further sorting.

Quick Sort Breakdown

Let's break down the quickSort function step by step:

Function Definition

This line defines the quickSort function that returns nothing. The function takes a slice of integers arr and two integers low and high as its parameters. These specify the sub-slice to be sorted. The function does not return anything, but the input arr becomes sorted.

Go
1func quickSort(arr []int, low, high int)

Base Case: Check if Sub-slice has More than One Element

The if condition ensures that the sub-slice has more than one element to sort. If low is not less than high, the function returns without making any changes. This is the base case for the recursion.

Go
1if low < high

Partition the Sub-slice

Call the partition function to rearrange the elements so that all elements less than the pivot are on the left, and all elements greater are on the right. The function returns the index of the pivot element in its correct sorted position.

Go
1pi := partition(arr, low, high)

Recursively Sort Elements Before the Pivot

Recursively call the quickSort function on the sub-slice of elements before the pivot index. This ensures that this left sub-slice gets sorted.

Go
1quickSort(arr, low, pi-1)

Recursively Sort Elements After the Pivot

Recursively call the quickSort function on the sub-slice of elements after the pivot index. This ensures that this right sub-slice gets sorted.

Go
1quickSort(arr, pi+1, high)

In summary, the quickSort function sorts a slice by using a divide-and-conquer strategy. It first partitions the slice around a pivot element, placing the pivot in its correct position. Then, it recursively sorts the sub-slices formed around the pivot. The base case ensures that sub-slices with one or zero elements do not need further sorting, allowing the recursion to terminate.

Practice Time

Great job learning about quick sort! These foundational algorithms will not only reinforce your understanding of the sorting principle but are often used as a stepping stone to understand more complex algorithms. Happy learning, and let's sort it out!

Enjoy this lesson? Now it's time to practice with Cosmo!

Practice is how you turn knowledge into actual skills.