Go sort a slice of runes?

Question

I'm having trouble sorting strings by character (to check whether two strings are anagrams, I want to sort both of them, and check for equality).

I can get a []rune representation of the string s like this:

runes := make([]rune, len(s)) 
copy(runes, []rune(s))

And I can sort ints like this

someInts := []int{5, 2, 6, 3, 1, 4} // unsorted
sort.Ints(someInts)

But rune is just an alias for int32 so I should be able to call

sort.Ints(runes) 

However, I get the error:

cannot use runes (type []rune) as type []int in function argument

So... how do I sort a slice of int32, int64, or int*?

EDIT: I did get my runes sorted, but boy, this is ugly.

type RuneSlice []rune

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

func sorted(s string) string {
    runes := []rune(s)
    sort.Sort(RuneSlice(runes))
    return string(runes)
}

So basically if you have a slice of whatever, you'll have to wrap it in a type that implements sort.Interface. All those implementations will have the exact same method bodies (like sort.IntSlice and sort.Float64Slice). If this is really how ugly this has to be then why didn't they provide these WhateverSlice wrappers in the sort package? The lack of generics start to hurt very badly now. There must be a better way of sorting things.

Answer 1

Use sort.Sort(data Interface) and implement sort.Interface, see the examples on package documentation.

You cannot use rune which is int32 as int. Check the comment of int.

int is a signed integer type that is at least 32 bits in size. It is a distinct type, however, and not an alias for, say, int32.

Answer 2

Note: Go 1.8 will introduce helpers for sorting slices.
See issue 16721 and commit 22a2bdf by Brad Fitzpatrick

var strings = [...]string{"", "Hello", "foo", "bar", "foo", "f00", "%*&^*&^&", "***"}

func TestSlice(t *testing.T) {
    data := strings
    Slice(data[:], func(i, j int) bool {
        return data[i] < data[j]
    })
}

Answer 3

Just as a point of comparison, here's what things might look like if the sort interface were slightly different. That is, rather than the interface being on the container, what would things look like if the interface were on the elements instead?

package main

import (
    "fmt"
    "sort"
)

type Comparable interface {
    LessThan(Comparable) bool
}

type ComparableSlice []Comparable

func (c ComparableSlice) Len() int {
    return len(c)
}

func (c ComparableSlice) Less(i, j int) bool {
    return c[i].LessThan(c[j])
}

func (c ComparableSlice) Swap(i, j int) {
    c[i], c[j] = c[j], c[i]
}

func SortComparables(elts []Comparable) {
    sort.Sort(ComparableSlice(elts))
}

//////////////////////////////////////////////////////////////////////
// Let's try using this:

type ComparableRune rune

func (r1 ComparableRune) LessThan(o Comparable) bool {
    return r1 < o.(ComparableRune)
}

func main() {
    msg := "Hello world!"

    comparables := make(ComparableSlice, len(msg))
    for i, v := range msg {
        comparables[i] = ComparableRune(v)
    }

    SortComparables(comparables)

    sortedRunes := make([]rune, len(msg))
    for i, v := range comparables {
        sortedRunes[i] = rune(v.(ComparableRune))
    }

    fmt.Printf("result: %#v\n", string(sortedRunes))
}

Here, we define a Comparable interface, and we get our type ComparableRune to satisfy it. But because it's an interface, we've got to do the awkward boxing to go from rune to ComparableRune so that dynamic dispatch can kick in:

    comparables := make(ComparableSlice, len(msg))
    for i, v := range msg {
        comparables[i] = ComparableRune(v)
    }

and unboxing to get back our runes:

    sortedRunes := make([]rune, len(msg))
    for i, v := range comparables {
        sortedRunes[i] = rune(v.(ComparableRune))
    }

This approach appears to require us to know how to do typecasts to go back and forth between the interface and the dynamic type of the value. It seems like we would need to use more parts of Go---more mechanics---than the approach that uses the container as the interface.

Answer 4

There is, in fact a soft-generic way to do what you want.

Check out the following package:

https://github.com/BurntSushi/ty/tree/master/fun

especially the following file:

https://github.com/BurntSushi/ty/blob/master/fun/sort_test.go

Example of how it is used:

tosort := []int{10, 3, 5, 1, 15, 6}

fun.Sort(func(a, b int) bool {
    return b < a
}, tosort)

There are lots of other interesting fun generic algorithms implemented through reflection in that package.

All credits go to @BurntSushi.

Answer 5

As of November 2020 at least, https://golang.org/pkg/sort/ offers to use a custom Less function passed as a closure. The code below has the desired effect:

package main

import (
    "fmt"
    "sort"
)

func main() {

    s1 := "eidbaooo"

    runeSlice := []rune(s1)

    fmt.Println(string(runeSlice))

    sort.Slice(runeSlice, func(i, j int) bool {
        return runeSlice[i] < runeSlice[j]
    })
    
    fmt.Println(string(runeSlice))
}

Output:

eidbaooo
abdeiooo

This can spare you the full interface implementation.