Sorting in Go from JavaScript
Tags: codenewbie, beginners, go, javascript
Published: 2020-05-25 16:50:56

---
title: Sorting in Go from JavaScript
published: true
description: 
tags: #codenewbie, #beginners, #go, #javascript
---

In computer science, **sorting** means taking a collection of items, and rearranging them so they are in a specified order, for example sorting a list of strings alphabetically, numbers from smallest to largest, or sorting structs by one of their fields. You can use this for things like making the inner workings of your algorithms more efficiently, or displaying data in a certain order (ex listing search results from newest to oldest).

For sorting in Go, the standard library provides the `sort` package to efficiently implement sorting for your data, and it makes cool use of Go interfaces to define the rules to sorting data. And it'll be familiar if you've used JavaScript's `Array.prototype.sort` method!

## 💬 Sorting strings

Let's start off with a slice of strings we want to sort in alphabetical order:

```go
var languages = []string{"Go", "C", "Ruby", "JavaScript", "XML"}
```

In JavaScript, sorting them would look something like this:

```javascript
let languages = ["Go", "C", "Ruby", "JavaScript", "XML"];

languages.sort();
console.log(languages); // ["C", "Go", "JavaScript", "Ruby", "XML"]
```

Since `languages` is an array, we can use `Array.prototype.sort`, to put them in order.

Since unlike JS arrays, Go slices don't have methods out of the box, instead of using an array sort method, we import the sort package and use its `Sort` function to rearrange our slices. Let's give it a try! Put this code in a file called `sort-strings.go`

```go
package main

import (
    "fmt"
    "sort"
)

func main() {
    languages := []string{"Go", "C", "Ruby", "JavaScript", "XML"}
    sort.Sort(languages)

    fmt.Println(languages)
}
```

Then if you run `go run sort-strings.go`, you should get:

```
./sort-strings.go:10:14: cannot use languages (type []string) as type sort.Interface in argument to sort.Sort:
	[]string does not implement sort.Interface (missing Len method)
```

A compiler error? The reason why that is, is because `sort.Sort` doesn't automatically take in a slice type. Its function signature actually looks like this:

```go
func Sort(data Interface)
```

`sort.Interface` (with a big I) is a Go interface that represents **a collection of data that can be sorted**, like a list of strings, numbers, or even structs. And since sorting slices of strings and ints is common, the sort package gives you some built-in types that make slices of strings or ints compatible with `sort.Sort`. Try this out!

```diff
  func main() {
      languages := []string{"Go", "C", "Ruby", "JavaScript", "XML"}
-     sort.Sort(languages)
+     sort.Sort(sort.StringSlice(languages))

      fmt.Println(languages)
  }
```

`sort.StringSlice` is a slice of strings, but it has the methods needed to implement `sort.Interface`. So by converting a `[]string` to a StringSlice, it can be sorted with `sort.Sort`!  And now if you do `go run sort-strings.go`, you should see the list of programming languages in alphabetical order!

Why do we need a special interface, though, to be able to sort data, instead of Go just having `sort.Sort` take in slices? The reason why is because if we pass in a collection of items, Go needs a way of knowing what order the items go in. And to **write those rules** to sorting your slice, you implement the `sort.Interface`'s methods. As you will see, Interface gives us flexibility to define the order of items whatever way you like!

## 🎨 Making a custom sort type

Let's say our `languages` slice included "fish" (a shell scripting language). If you're sorting that slice of programming tools in alphabetical order, it would make sense for the sorted slice to look like this:

```
[C, fish, Go, JavaScript, Ruby, XML]
```

But instead, "fish" goes last, even after XML! With `sort.StringSlice`, and same for sorting a list of strings in JS with `Array.prototype.sort`, the default sorting behavior is **lexicographic** order, not alphabetical order. And in lexicographic order, lowercase letters like the f in fish come after uppercase letters like the X in XML. If we want to sort by letter of the alphabet in a case-insensitive way, we need to implement some custom behavior. What would that look like?

To make custom sorting rules, we need to think about what sorting does. We're not going to look into the details of the different sorting algorithms like quicksort, mergesort, and bubblesort in this tutorial, but learning them is important in coding. The important thing you need to know about sorting algorithms for writing custom sorting rules in Go and JS, though, is that they need to:

1. Look at items in the collection
2. **Compare** them to see which ones should go first
3. Put the items in order based on those comparisons

In JavaScript, you would pass a custom function in to tell `sort` how to do comparisons between pairs of items in the array, like this:

```javascript
languages.sort((langA, langB) => {
  langA = langA.toLowerCase();
  langB = langB.toLowerCase();
  if (langA < langB) {
    return -1; // return -1 if langA should go before langB in the array
  } else if (langB > langA) {
    return 1;  // return 1 if langB should go before langA in the array
  }
  return 0;    // return 0 if they can go in either order
})
```

Because we used `toLowerCase` before comparing languages, the language `fish` in all-lowercase does go before the capitalized Go, JavaScript, Ruby, and XML, but after C!

Now if we look at the Go `sort.Interface`, we'll see the methods we need to implement are pretty similar:

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

So to make a type that can be sorted, we need to implement the `sort.Interface` so it can:

1. Tell Go's sort package the collection's `Len`gth
2. Take any two items in the collection (items `i` and `j`), and `Swap` them
3. Look at any two items in the collection and see which one should go first when the collection is sorted, with `Less`

Let's start by implementing `Len` and `Swap`.

```go
type alphabeticalStrings []string

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

func (a alphabeticalStrings) Swap(i, j int) {
    placeholder := a[j]
    a[j] = a[i]
    a[i] = placeholder
}
```

First, we define a type, `alphabeticalStrings`, on top of a string slice. By defining our own type in Go, we can write methods for it.

For `Len`, we just use Go's built-in `len` function to get how long our slice is, and for `Swap`, we swap two items in the slice. So far so good. Now let's implement `Less`. Import the `strings` package, and add in this function:

```go
func (a alphabeticalStrings) Less(i, j int) bool {
    return strings.ToLower(a[i]) < strings.ToLower(a[j])
}
```

Notice something about the `Less` method? It looks an awful lot like that comparison method we made for `Array.prototype.sort`, except it returns a bool instead of an int and takes in slice indices instead of items!

Now, let's try it out! Edit the `main` function like this:

```diff
  func main() {
      languages := []string{"Go", "C", "fish", "Ruby", "JavaScript", "XML"}
-     sort.Sort(sort.StringSlice(languages))
+     sort.Sort(alphabeticalStrings(languages))

      fmt.Println(languages)
  }
```

And if you run `go run sort-strings.go`, now you should see the list sorted as expected!

```
[C, fish, Go, JavaScript, Ruby, XML]
```

You know what's cool about Go's `sort.Interface`? Both the alphabeticalStrings type we wrote and the StringSlice type the Go Team wrote are built on top of a plain old `[]string` and can both be passed into `sort.Sort`. We can pick which order we want the strings in by picking which type we convert our slice of strings to!

## 😎 Simplify our sorting with sort.Slice!

One difference between the JS and Go versions of `sort`, was that to sort a Go slice, in addition to a comparison function, we needed to write those `Len` and `Swap` methods. And for any slice type, Len and Swap pretty much will always look the same. So to define a new sorting order, it feels kinda cumbersome to have to implement all three methods.

The reason for three methods is, the data structure you're implementing `sort.Interface` for **doesn't necessarily have to be an array or slice**. I've only used the sort package on slices, but you could implement a `sort.Interface` with some other type, like a linked list.

But for slices, where we're always using the same logic for Len and Swap, what if we only needed to implement `Less`, just like in JavaScript? The sort package has just the method to do that, `sort.Slice`!

```go
func Slice(
    slice interface{},
    less func(i, j int) bool,
)
```

We pass in our slice of data that we want to sort as the first argument, and a function to compare the slice's item with as the second argument. Now we can sort our data without even making a new type! Let's try refactoring our main function one more time to try that out:

```diff
  func main() {
      languages := []string{"Go", "C", "fish", "Ruby", "JavaScript", "XML"}
-     sort.Sort(alphabeticalStrings(languages))
+     sort.Slice(languages, func(i, j int) bool {
+         return strings.ToLower(languages[i]) < strings.ToLower(languages[j])
+     })

      fmt.Println(languages)
  }
```

All right! We've got our sorted slice!

Something else cool about the sort package, in addition to us being able to pick which order we're sorting by, notice that in sort.Sort and sort.Slice, we didn't need to know which sorting algorithm we're using. `sort.Sort` handles implementing the algorithm, and all the function needs to know from us is how to compare items, how to swap them, and how many items we have. That's interfaces in action!

By the way, being familiar with how sorting algorithms work is still definitely worthwhile since you'll know the clever techniques to having your computer do less work to arrange data, and since sorting is used everywhere. So if you want to learn how they work and what `sort.Sort` is doing behind the scenes with those functions we wrote, Below is some materials on the algorithms themselves.

* [Free Code Camp - Sorting Algorithms Explained](https://www.freecodecamp.org/news/sorting-algorithms-explained/)
* [Toptal - Sorting Algorithm Animations](https://www.toptal.com/developers/sorting-algorithms)
* [Implementing Sorting Algorithms in JavaScript](https://medium.com/@rwillt/implementing-sorting-algorithms-in-javascript-b08504cdf4a9)