Alphanumeric sort

Suppose we have some strings in our Go program that contain both numbers and letters in them. We want to sort the strings, but want the numbers to be considered.

In alphanumeric sorting, a string that starts with "1" will come before a string that starts with "10" or "100". In Go, we can implement the Less() method and call sort.Sort.

This Go program performs an alphanumeric sort with a reusable type that handles sorting. It uses rune slices, not byte accesses, to improve Unicode handling.

Part 1 In the ByAlphanumeric type's Less() method, we need to determine if one element is less than another. We first create rune slices.

Part 2 We iterate through both strings separately, as we need to collect chunks that can be compared (not just runes or chars).

Part 3 Here we collect all runes that return true for IsDigit, so we collect an entire integer or non-integer chunk.

Part 4 We collect the chunk for the other rune slice with equivalent logic. We call the same method for each of the chunks.

Part 5 Once we have the 2 chunks, we convert them into strings, which allows to either parse them as integers, or compare them directly.

Part 6 In main() we see how to create the ByAlphanumeric type from a string slice and sort the strings alphanumerically.

package main

import (
    "fmt"
    "sort"
    "strconv"
    "strings"
    "unicode"
)

type ByAlphanumeric []string

func (a ByAlphanumeric) Len() int { return len(a) }
func (a ByAlphanumeric) Less(i, j int) bool {
    // Part 1: get runes for each string to sort them.
    runes1 := []rune(a[i])
    runes2 := []rune(a[j])
    marker1 := 0
    marker2 := 0

    for {
        // Part 2: iterate through the strings with two markers.
        if marker1 >= len(runes1) || marker2 >= len(runes2) {
            break
        }

        // Part 3: collect all runes of digit type or not.
        space1 := a.GetChunk(runes1, &marker1)

        // Part 4: collect all digit or non-digit runes for the other string.
        space2 := a.GetChunk(runes2, &marker2)

        // Part 5: compare the 2 chunks based on integers or strings based on their contents.
        str1 := string(space1)
        str2 := string(space2)
        result := false
        equal := false
        if unicode.IsDigit(space1[0]) && unicode.IsDigit(space2[0]) {
            chunk1, _ := strconv.Atoi(str1)
            chunk2, _ := strconv.Atoi(str2)
            equal = chunk1 == chunk2
            result = chunk1 < chunk2
        } else {
            equal = strings.Compare(str1, str2) == 0
            result = strings.Compare(str1, str2) < 0
        }
        if !equal {
            return result
        }
    }
    return len(runes1) < len(runes2)
}
func (a ByAlphanumeric) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a ByAlphanumeric) GetChunk(runes []rune, marker *int) []rune {
    c := runes[*marker]
    space := []rune{}
    for {
        space = append(space, c)
        *marker += 1
        if *marker < len(runes) {
            c = runes[*marker]
        } else {
            break
        }
        if unicode.IsDigit(c) != unicode.IsDigit(space[0]) {
            break
        }
    }
    return space
}

func main() {
    // Part 6: use the alphanumeric sorting algorithm.
    highways := []string{"100F", "50F", "SR100", "SR9"}
    fmt.Println(highways)
    sort.Sort(ByAlphanumeric(highways))
    fmt.Println(highways)
}[100F 50F SR100 SR9]
[50F 100F SR9 SR100]

Summary

With an alphanumeric sorting method, we can sort strings logically based on integers as well as character groups. The algorithm considers sequences of runes as integers.