How to Sort in Go? The Ultimate Guide to Golang Sort Package Read it later

Sorting is a concept that you encounter wherever you go, especially in the world of computer science. It holds immense importance, and it’s crucial to have a good understanding of it. In this blog, we will embark on a journey to learn how to sort in Go. But wait, it’s not just about sorting Golang integers, floats, or strings; we’ll also explore sorting custom data types and even dive into complex data structures. By the time you finish reading this blog, we assure you that you’ll have a strong grasp of the concept.

Now, you might be wondering if we’re going to build sorting algorithms from scratch. Well, fear not! We will be leveraging the power of Go’s built-in sort package. So, without further ado, let’s take a deep dive into the vast pool of knowledge that awaits us.

Golang Sort Package

The sort package in Go is a powerful built-in package that provides a collection of methods and interfaces for sorting different types of data. It was developed to simplify the process of sorting elements in a Go program and to offer efficient sorting algorithms out of the box.

The sort package was included in Go starting from version 1.0, making it readily available for developers to use in their projects. To begin using the sort package, you need to import it into your Go program. Here’s how you can do that:

import "sort"

By including this import statement at the beginning of your Go code, you gain access to the various sorting functions and methods provided by the sort package.

The sort package is designed to handle sorting operations on slices, which are dynamic arrays in Go. Using the functions and methods from this package, you can easily sort slices of integers, floats, strings, or even custom data types according to your specific requirements.

Go Sort Ints

Go sort’s Ints function is designed to sort a slice of integers in increasing order. It takes a slice of int values as input and modifies the slice in place to reflect the sorted order.

Let’s take a look at the syntax and an example to understand it better.

Syntax:

func Ints(x []int)

Example:

func main() {
	// Unsorted Array
	s := []int{5, 8, 3, 2, 7, 1}
	sort.Ints(s)
	fmt.Println(s)
}

Output:

[1 2 3 5 7 8]

In the example above, we have an unsorted slice of integers s. We call the sort.Ints function, passing the slice s as an argument. After the function call, the s slice is sorted in increasing order.

Check if Int Slice/Array is Sorted

If you want to check whether a slice of int values is already sorted in increasing order, you can use the IntsAreSorted function. Let’s explore its syntax and an example.

Syntax:

func IntsAreSorted(x []int) bool

Example:

func main() {
	// Sorted in Ascending order
	s := []int{1, 2, 3, 4, 5}
	fmt.Println(sort.IntsAreSorted(s))

	// Sorted in Descending order
	s = []int{5, 4, 3, 2, 1}
	fmt.Println(sort.IntsAreSorted(s))

	// Unsorted order
	s = []int{4, 2, 3, 1, 5}
	fmt.Println(sort.IntsAreSorted(s))
}

Output:

true
false
false

In the example above, we have three different scenarios. The first slice s is already sorted in ascending order, so the output is true. The second slice s is sorted in descending order, resulting in an output of false. The third slice s is completely unsorted, leading to another output of false.

Search in Ints Array/Slice

Now let’s explore how to search for an integer value in a sorted slice using the SearchInts function. This function returns the index at which the value is found or the index where it should be inserted to maintain the sorted order.

Syntax:

func SearchInts(a []int, x int) int

Example:

func main() {
	a := []int{1, 2, 3, 4, 5}

	x := 3
	i := sort.SearchInts(a, x)
	fmt.Printf("%d found at index %d in %v\n", x, i, a)

	x = 6
	i = sort.SearchInts(a, x)
	fmt.Printf("%d not found, can be inserted at index %d in %v\n", x, i, a)
}

Output:

3 found at index 2 in [1 2 3 4 5]
6 not found, can be inserted at index 5 in [1 2 3 4 5]

In this example, we have a sorted slice a containing integers. We use sort.SearchInts to search for the value x within the slice. If the value is found, the function returns the index of its occurrence. If the value is not found, the function returns the index where it should be inserted to maintain the sorted order.

In the first scenario, we search for x = 3 in the a slice and the function returns the index 2 since 3 is found at that position. In the second scenario, we search for x = 6, which is not present in the slice. The function returns 5, indicating that 6 can be inserted at the index 5 while preserving the sorted order of the slice.

Golang Sort Floats

Sorting floating-point numbers in Go is made simple with the sort.Float64s function. This function allows us to sort a slice of float64s in ascending order.

Let’s take a look at the syntax and an example of how to use it:

Syntax:

func Float64s(x []float64)

Example:

func main() {
	s := []float64{+1.2, 0.0, -0.3, 2.9, -0.18, 8.4}
	sort.Float64s(s)
	fmt.Println(s)

	s = []float64{math.Inf(1), math.NaN(), math.Inf(-1), 0.0}
	sort.Float64s(s)
	fmt.Println(s)
}

Output:

[-0.3 -0.18 0 1.2 2.9 8.4]
[NaN -Inf 0 +Inf]

As you can see, sort.Float64s has efficiently sorted the slices. It places the not-a-number (NaN) values before other numeric values.

Check If Float64 Slice is Sorted

To check whether a given float64 slice is sorted in increasing order, we can use the sort.Float64sAreSorted function.

Syntax:

func Float64sAreSorted(x []float64) bool

Example:

func main() {
	s := []float64{math.NaN(), math.Inf(-1), 0.0, 0.9, 1.5, 3.8, 5.2, math.Inf(1)}
	fmt.Println(sort.Float64sAreSorted(s))

	s = []float64{math.Inf(-1), 5.2, 3.8, 1.5, 0.9, 0.0, math.Inf(-1), math.NaN()}
	fmt.Println(sort.Float64sAreSorted(s))

	s = []float64{0.9, 0.0, math.Inf(-1), 1.5, math.NaN(), 3.8, math.Inf(-1), 5.2}
	fmt.Println(sort.Float64sAreSorted(s))
}

Output:

true
false
false

The sort.Float64sAreSorted function confirms if the slice is sorted correctly.

Search Float64 in Sorted Slice/Array

Lastly, if we need to find an element within a sorted slice, we can utilize the sort.SearchFloat64s function.

Syntax:

func SearchFloat64s(a []float64, x float64) int

Example:

func main() {
	s := []float64{math.NaN(), math.Inf(-1), 0.0, 0.9, 1.5, 3.8, 5.2, math.Inf(1)}

	x := 1.5
	i := sort.SearchFloat64s(s, x)
	fmt.Printf("found %g at index %d in %v\n", x, i, s)

	x = 0.5
	i = sort.SearchFloat64s(s, x)
	fmt.Printf("%g not found, can be inserted at index %d in %v\n", x, i, s)
}

Output:

found 1.5 at index 4 in [NaN -Inf 0 0.9 1.5 3.8 5.2 +Inf]
0.5 not found, can be inserted at index 3 in [NaN -Inf 0 0.9 1.5 3.8 5.2 +Inf]

The sort.SearchFloat64s function allows us to locate a specific float64 value within the sorted slice. It returns the index where the element is found or the index where it can be inserted to maintain the sorted order.

Go Sort Strings

To sort a slice of strings in increasing order, we can use the sort.Strings function. This function rearranges the elements in the slice according to lexicographical order.

Syntax:

func Strings(x []string)

Here’s an example that demonstrates how to use the sort.Strings function:

import (
	"fmt"
	"sort"
)

func main() {
	s := []string{"Hello", "World", "Go", "Programming", "Language"}
	sort.Strings(s)
	fmt.Println(s)
}

Output:

[Go Hello Language Programming World]

In this example, we have a slice of strings named s. By calling sort.Strings(s), the elements in the s slice will be sorted in increasing order based on the lexicographical comparison. Finally, we print the sorted s slice, which will output [Go Hello Language Programming World].

If you need to check whether a given slice of strings is already sorted in increasing order, you can use the sort.StringsAreSorted function.

Syntax:

func StringsAreSorted(x []string) bool

The StringsAreSorted function returns a boolean value indicating whether the input slice x is sorted in increasing order. It can be useful to verify the order of your data before performing any further operations.

Additionally, if you have a sorted slice of strings and want to search for a specific string x, you can use the sort.SearchStrings function.

Syntax:

func SearchStrings(a []string, x string) int

The SearchStrings function searches for the string x within a sorted slice of strings a and returns the index where the string is found. If the string is not present in the slice, the function returns the index at which it can be inserted while maintaining the sorted order.

Deep Dive Into Go Sort Interface

The Go sort package introduces us to a fascinating built-in interface called Interface. This interface serves as a foundation for sorting in Go. By implementing this interface, we can sort a collection of elements using the routines provided by the sort package. Let’s explore the Interface type and its methods to gain a deeper understanding.

Sort Interface Implementation

The Interface type consists of three essential methods that we need to implement in order to utilize the sorting capabilities of the package. These methods allow us to define the behavior of sorting for our specific collection.

Here’s the implementation of the Interface type:

type Interface interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
}

• Len() int: The Len() method returns the number of elements in the collection. It provides the necessary information for sorting routines to determine the range of elements to be sorted.
• Less(i, j int) bool: The Less() method compares two elements at indices i and j and determines whether the element at index i should be sorted before the element at index j. It returns true if the element at index i is considered smaller than the element at index j.
• Swap(i, j int): The Swap() method swaps the positions of the elements at indices i and j. It facilitates the reordering of elements during the sorting process.

Example

To illustrate how to implement the Interface, let’s consider an example:

import (
	"fmt"
	"sort"
)

type IntArray []int

func (a IntArray) Len() int {
	return len(a)
}

func (a IntArray) Less(i, j int) bool {
	return a[i] < a[j]
}

func (a IntArray) Swap(i, j int) {
	a[i], a[j] = a[j], a[i]
}

func main() {
	var a sort.Interface = IntArray{2, 1, 7, 3, 6, 5}
	fmt.Println(sort.IsSorted(a))
	sort.Sort(a)
	fmt.Println(a)
	fmt.Println(sort.IsSorted(a))
}

In this example, we define a custom type IntArray, which is a slice of integers. We then implement the Len(), Less(i, j int), and Swap(i, j int) methods for this type. These methods define how the IntArray should be sorted. In this case, we sort the elements in ascending order.

Within the main() function, we create an instance of sort.Interface named a, initialized with an IntArray. We first check if the a is sorted using the sort.IsSorted() function, which returns false since the elements are not yet sorted. We then invoke sort.Sort(a) to sort the IntArray in-place. Finally, we print the sorted IntArray and verify its sorted state using sort.IsSorted().

Output:

false
[1 2 3 5 6 7]
true

By implementing the Interface methods according to our specific sorting requirements, we gain control over the sorting behavior for any custom type we define.

Sorting in Descending Order

In the previous sections, we discussed functions, such as Ints, Float64s, and Strings, which focused on sorting in ascending order. However, sometimes we may need to sort our data in descending order. Fortunately, with a simple tweak, we can achieve this and gain more control over the sorting implementation.

To sort in descending order, we need to modify the Less(i, j int) bool function. In this function, we compare two elements and determine their order. By changing the comparison operator from < to >, we can reverse the sorting order.

Let’s take a look at the modified Less function for sorting integers in descending order:

func (a IntArray) Less(i, j int) bool {
	return a[i] > a[j]
}

By making this small change, we can now obtain a sorted array in descending order. The > operator ensures that elements are arranged from the highest to the lowest value.

Output:

[7 6 5 3 2 1]

Reverse Function in Go Sort Package

Another useful function provided by Go’s sort package is the Reverse function. It allows us to reverse the order of elements in a sorted collection. This can be particularly handy in scenarios where we need to present data in descending order.

The Reverse function follows a simple syntax:

func Reverse(data Interface) Interface

When using the Reverse function, we pass a sort.Interface type as the argument, and it returns another sort.Interface representing the reversed order of the elements.

Let’s continue with the example of the IntArray type we used earlier:

func main() {
	var a sort.Interface = IntArray{2, 1, 7, 3, 6, 5}

	var rev sort.Interface = sort.Reverse(a)
	sort.Sort(rev)
	fmt.Println("Reversed Order: ", rev)
	fmt.Println("Is Sorted: ", sort.IsSorted(rev))
	fmt.Println("Type: ", reflect.TypeOf(rev))
}

In this example, we declare a variable a of type sort.Interface and initialize it with an instance of IntArray. We then create another variable rev by applying the sort.Reverse function to a. Next, we call sort.Sort(rev) to sort rev in reverse order. Finally, we print the reversed order, check if it is sorted, and display its type using the reflect package’s TypeOf function.

The output of the above code will be:

Reversed Order:  &{[7 6 5 3 2 1]}
Is Sorted:  true
Type:  *sort.reverse

As you can see, the Reverse function successfully reverses the order of the elements in the IntArray. The reversed order is printed, and we verify its sorted state using the sort.IsSorted function. Additionally, we confirm the type of rev using the reflect package’s TypeOf function, which indicates that it is of type *sort.reverse.

Sorting Slices in Golang

Go’s sort package provides a powerful function called Slice that allows you to sort slices of any type. Here’s the syntax for using the Slice function:

func Slice(x any, less func(i, j int) bool)

The Slice function sorts the slice x using the provided less function. It’s important to note that x must be a slice, otherwise, the function will panic.

It’s worth mentioning that the sort performed by Slice is not guaranteed to be stable. This means that equal elements may be reversed from their original order. If you require a stable sort, you can use the SliceStable function instead.

The less function passed to Slice must satisfy the same requirements as the Less method of the Interface type.

Let’s look at an example that demonstrates how you can use the Slice function to sort an array in descending order:

func main() {
	iarr := []int{5, 1, 3, 2, 4}

	sort.Slice(iarr, func(i, j int) bool {
		return iarr[i] > iarr[j]
	})

	fmt.Println(iarr) // Output: [5 4 3 2 1]
}

In this example, we declare an integer slice named iarr with some unsorted values. We then pass a lambda function to the Slice function, which compares the elements in reverse order (i.e., descending). Finally, we print the sorted iarr slice, which will be [5 4 3 2 1].

Alternatively, we can define the less function separately and pass it to the Slice function:

func main() {
	iarr := []int{5, 1, 3, 2, 4}

	less := func(i, j int) bool {
		return iarr[i] > iarr[j]
	}

	sort.Slice(iarr, less)

	fmt.Println(iarr)
}

By defining the less function outside of the Slice function call, we can reuse it or modify it more easily.

Check if Slice is Sorted

You can also check whether a slice is sorted using the SliceIsSorted function.

Here’s an example that demonstrates its usage:

func main() {
	unsorted_arr := []int{5, 1, 3, 2, 4}
	sorted_arr_asc := []int{1, 2, 3, 4, 5}
	sorted_arr_desc := []int{5, 4, 3, 2, 1}

	fmt.Println(sort.SliceIsSorted(unsorted_arr, func(i, j int) bool {
		return unsorted_arr[i] < unsorted_arr[j]
	})) // false

	fmt.Println(sort.SliceIsSorted(sorted_arr_asc, func(i, j int) bool {
		return sorted_arr_asc[i] < sorted_arr_asc[j]
	})) // true

	fmt.Println(sort.SliceIsSorted(sorted_arr_desc, func(i, j int) bool {
		return sorted_arr_desc[i] < sorted_arr_desc[j]
	})) // false
}

In this example, we have three slices: unsorted_arr, sorted_arr_asc, and sorted_arr_desc. We use the SliceIsSorted function along with the appropriate less function to check if each slice is sorted. The function returns true if the slice is sorted and false otherwise.

Golang Sort Package: Built-in Slice Types

In addition to the sort.Interface type that we discussed earlier, the sort package in Go also provides built-in types specifically designed for sorting slices of integers, floats, and strings. These types simplify the process of sorting and eliminate the need to implement the sort.Interface methods manually.

Here are the built-in sort Slice types for different data types:

• IntSlice: This type, defined as type IntSlice []int, is used for sorting slices of integers.
• Float64Slice: For sorting slices of float64 values, we have the Float64Slice type, defined as type Float64Slice []float64.
• StringSlice: When it comes to sorting slices of strings, we can utilize the StringSlice type, which is defined as type StringSlice []string.

By using these built-in types, we can take advantage of the methods already implemented on them, such as Sort(), Len(), Less(), Swap(), and Search(). Let’s explore an example that demonstrates the usage of these built-in types:

func main() {
	var iarr sort.IntSlice = []int{5, 1, 3, 2, 4}
	iarr.Sort()
	fmt.Println("Sorted: ", iarr)
	fmt.Println("Len: ", iarr.Len())
	fmt.Println("Less: ", iarr.Less(0, 1))
	iarr.Swap(0, 1)
	fmt.Println("After Swapping: ", iarr)
	fmt.Println("Found 3 at Index: ", iarr.Search(3))

	var farr sort.Float64Slice = []float64{5.5, 1.1, 3.3, 2.2, 4.4}
	farr.Sort()
	fmt.Println("Sorted: ", farr)
	fmt.Println("Len: ", farr.Len())
	fmt.Println("Less: ", farr.Less(0, 1))
	farr.Swap(0, 1)
	fmt.Println("After Swapping: ", farr)
	fmt.Println("Found 3.3 at Index: ", farr.Search(3.3))

	var sarr sort.StringSlice = []string{"e", "a", "c", "b", "d"}
	sarr.Sort()
	fmt.Println("Sorted: ", sarr)
	fmt.Println("Len: ", sarr.Len())
	fmt.Println("Less: ", sarr.Less(0, 1))
	sarr.Swap(0, 1)
	fmt.Println("After Swapping: ", sarr)
	fmt.Println("Found c at Index: ", sarr.Search("c"))
}

In this example, we declare and initialize slices of integers, floats, and strings. We then assign them to their respective built-in sort types: IntSlice, Float64Slice, and StringSlice. We can now directly call the methods on these types to sort, retrieve the length, compare elements, swap elements, and search for specific values within the slices.

Output:

Sorted:  [1 2 3 4 5]
Len:  5
Less:  true
After Swapping:  [2 1 3 4 5]
Found 3 at Index:  2

Sorted:  [1.1 2.2 3.3 4.4 5.5]
Len:  5
Less:  true
After Swapping:  [2.2 1.1 3.3 4.4 5.5]
Found 3.3 at Index:  2

Sorted:  [a b c d e]
Len:  5
Less:  true
After Swapping:  [b a c d e]
Found c at Index:  2

Additionally, if you have existing slices of integers, floats, or strings, you can convert them to the respective built-in sort types using type conversion.

Here’s an example that demonstrates the conversion process:

func main() {
	iarr := []int{5, 1, 3, 2, 4}
	farr := []float64{5.5, 1.1, 3.3, 2.2, 4.4}
	sarr := []string{"e", "a", "c", "b", "d"}

	intSlice := sort.IntSlice(iarr)
	floatSlice := sort.Float64Slice(farr)
	strSlice := sort.StringSlice(sarr)

	fmt.Println(reflect.TypeOf(intSlice))
	fmt.Println(reflect.TypeOf(floatSlice))
	fmt.Println(reflect.TypeOf(strSlice))
}

In this example, we declare slices of integers, floats, and strings. We then convert these slices to their respective built-in sort types using type conversion. Finally, we use the reflect.TypeOf() function to print the types of the converted variables.

Output:

sort.IntSlice
sort.Float64Slice
sort.StringSlice

Sorting Structs in Golang

Now that we have our basics clear, let’s move on to sorting some complex data structures. One common scenario is sorting a slice of structs in Go. Imagine we have a slice of Person structs, and we want to sort it based on the Age field. Sorting structs involves comparing the values of a specific field and rearranging the elements accordingly.

Here are two approaches to sorting a slice of structs in Go:

1. Using Interface Methods

We can define our own type for the slice of Person structs, let’s call it Persons. To enable sorting, we need to implement the Len(), Swap(i, j int), and Less(i, j int) bool methods for the Persons type.

type Person struct {
	Name string
	Age  int
}

type Persons []Person

func (p Persons) Len() int           { return len(p) }
func (p Persons) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
func (p Persons) Less(i, j int) bool { return p[i].Age < p[j].Age }

func main() {
	persons := Persons{
		{"John", 20},
		{"Jane", 30},
		{"Jack", 10},
	}

	sort.Sort(persons)

	fmt.Println(persons) // Output: [{Jack 10} {John 20} {Jane 30}]
}

In this approach, we define the Persons type as a slice of Person structs. By implementing the Len(), Swap(i, j int), and Less(i, j int) bool methods for the Persons type, we enable the sort.Sort function to sort the slice based on the Age field. The Less method defines the comparison logic for sorting, in this case, sorting in ascending order of age.

2. Using the Slice Function

Another approach to sorting structs in Go is by using the sort.Slice function. With this approach, we don’t need to define a custom type or implement any interface methods. We can directly use a slice of Person structs and provide a comparison function to the sort.Slice function.

type Person struct {
	Name string
	Age  int
}

func main() {
	persons := []Person{
		{"John", 20},
		{"Jane", 30},
		{"Jack", 10},
	}

	sort.Slice(persons, func(i, j int) bool {
		return persons[i].Age < persons[j].Age
	})

	fmt.Println(persons) // Output: [{Jack 10} {John 20} {Jane 30}]
}

In this approach, we define the slice of Person structs directly. We pass the persons slice and a comparison function to the sort.Slice function. The comparison function specifies the sorting order based on the Age field. The sort.Slice function handles the sorting process and modifies the original slice accordingly.

Sorting Map in Golang

Sorting a map is a common requirement when working with data in Go. While maps in Go are inherently unordered, there are methods we can use to sort them based on either the keys or the values. In this section, we will explore both approaches.

1. Sort by Key

Sorting a map by its keys involves extracting the keys, sorting them, and then accessing the corresponding values in the desired order. Let’s consider an example to illustrate this process:

package main

import (
	"fmt"
	"sort"
)

func main() {
	grades := map[string]int{
		"Alice":  85,
		"Bob":    92,
		"Charlie": 78,
	}

	keys := make([]string, 0, len(grades))
	for key := range grades {
		keys = append(keys, key)
	}

	sort.Strings(keys)

	for _, key := range keys {
		fmt.Printf("%s: %d\n", key, grades[key])
	}
}

In this example, we have a map called grades that associates students’ names with their scores. To sort the map by keys, we first create a slice called keys to store the keys of the grades map. We then iterate over the map using a range loop and append each key to the keys slice.

Next, we use the sort.Strings function to sort the keys slice in ascending order. Finally, we iterate over the sorted keys slice and print the corresponding values from the grades map.

2. Sort by Value

Sorting a map by its values involves a slightly different approach. Since maps are not designed for direct value-based sorting, we need to create a separate data structure to hold the key-value pairs, sort it based on the values, and then extract the sorted keys. Here’s an example to demonstrate this process:

package main

import (
	"fmt"
	"sort"
)

func main() {
	grades := map[string]int{
		"Alice":   85,
		"Bob":     92,
		"Charlie": 78,
	}

	type KeyValue struct {
		Key   string
		Value int
	}

	var keyValuePairs []KeyValue
	for key, value := range grades {
		keyValuePairs = append(keyValuePairs, KeyValue{Key: key, Value: value})
	}

	sort.Slice(keyValuePairs, func(i, j int) bool {
		return keyValuePairs[i].Value < keyValuePairs[j].Value
	})

	for _, kv := range keyValuePairs {
		fmt.Printf("%s: %d\n", kv.Key, kv.Value)
	}
}

In this example, we create a struct called KeyValue to hold the key-value pairs from the grades map. We initialize an empty slice of KeyValue structs called keyValuePairs. We then iterate over the grades map, create a KeyValue struct for each key-value pair, and append it to the keyValuePairs slice.

Next, we use the sort.Slice function to sort the keyValuePairs slice based on the values using a custom comparison function. Finally, we iterate over the sorted keyValuePairs slice and print the keys and values.

Wrapping Up

In conclusion, mastering sorting in Go is a valuable skill for efficient data organization. Go’s built-in sorting functions like sort.Ints, sort.Float64s, and sort.Strings enable easy sorting of integers, floats, and strings. Additionally, implementing the sort.Interface interface allows for custom sorting based on specific criteria.

With these techniques, you can enhance your Go programming capabilities and efficiently handle diverse data sets. Explore the Go documentation and experiment in the Go Playground to further refine your sorting skills. Happy coding and happy sorting!

Frequently Asked Questions (FAQs)

Reference

• Go Sort Package Docs