Sorting Algorithms in Go

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

Gopackage main import ( "fmt" ) // Partition function that makes use of pivot func partition(arr []int, low, high int) int { pivot := arr[high] // pivot i := low - 1 // Index of smaller element for j := low; j < high; j++ { // If the current element is smaller than or equal to the pivot 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 } // The main function that implements QuickSort func quickSort(arr []int, low, high int) { if low < high { // pi is the partitioning index, arr[pi] is now at the right place pi := partition(arr, low, high) // Separately sort elements before partition and after partition quickSort(arr, low, pi-1) quickSort(arr, pi+1, high) } } func main() { arr := []int{10, 7, 8, 9, 1, 5} n := len(arr) quickSort(arr, 0, n-1) fmt.Printf("Sorted array: %v\n", arr) // Sorted array: [1, 5, 7, 8, 9, 10] }package main import ( "fmt" ) // Partition function that makes use of pivot func partition(arr []int, low, high int) int { pivot := arr[high] // pivot i := low - 1 // Index of smaller element for j := low; j < high; j++ { // If the current element is smaller than or equal to the pivot 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 } // The main function that implements QuickSort func quickSort(arr []int, low, high int) { if low < high { // pi is the partitioning index, arr[pi] is now at the right place pi := partition(arr, low, high) // Separately sort elements before partition and after partition quickSort(arr, low, pi-1) quickSort(arr, pi+1, high) } } func main() { arr := []int{10, 7, 8, 9, 1, 5} n := len(arr) quickSort(arr, 0, n-1) fmt.Printf("Sorted array: %v\n", arr) // Sorted array: [1, 5, 7, 8, 9, 10] }

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

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.

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

func 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.

pivot := arr[high] // pivot

pivot := 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.

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

i := 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.

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

for 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.

if arr[j] <= pivot

if 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.

i++
arr[i], arr[j] = arr[j], arr[i]

i++
arr[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.

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

arr[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.

return i + 1

return 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.