自然順ソート別実装(Windows エクスプローラー準拠?)

2019/4/17 追記

改良版書きました!!

自然順ソート(マルチバイト対応改良版 & Windows エクスプローラー準拠) - bamch0h’s diary

前の記事 の最後に、ゼロパディングされた数値とそうでない数値が存在した場合に数値順に並んでくれないという問題があると書きました。今回はそれを解消したいと思います。

考え方としては単純で、文字列中の数値の部分を取り出して数値に変換したのちに大小比較をするだけです。もし数値が同じであれば桁数で比較して大小を決定します。

Goでの実装

今回もGoで実装しました。前回の記事から変更している部分は naturalSort0 の 数値かどうかを判定するif文の中のみです。数値の始まりと数値の終わりのインデックスを取得して、部分文字列を作成し、部分文字列を数値に変換したのち大小比較を行っています。初めは、比較結果がイコールだった場合は桁数も比較していたのですが、Windows の エクスプローラーの仕様と合わせるために削除しました。

package main

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

func getRune(s string, i int) (rune, int) {
    for x := i; x < len(s); x++ {
        if unicode.IsSpace(rune(s[x])) {
            continue
        }
        return rune(s[x]), x
    }
    return rune(0), len(s)
}

func natualSort0(a, b string) int {
    var ca, cb rune
    var ai, bi int
    for {
        if len(a) <= ai && len(b) <= bi {
            return 0
        }

        if len(a) <= ai {
            return -1
        }

        if len(b) <= bi {
            return 1
        }

        ca, ai = getRune(a, ai)
        cb, bi = getRune(b, bi)

        if unicode.IsDigit(ca) && unicode.IsDigit(cb) {
            aj := ai + 1
            for len(a) > aj {
                if !unicode.IsDigit(rune(a[aj])) {
                    aj--
                    break
                }
                aj++
            }

            bj := bi + 1
            for len(b) > bj {
                if !unicode.IsDigit(rune(b[bj])) {
                    bj--
                    break
                }
                bj++
            }

            sa := a[ai:aj]
            if sa == "" {
                sa = string(a[ai])
            }
            ia, _ := strconv.Atoi(sa)

            sb := b[bi:bj]
            if sb == "" {
                sb = string(b[bi])
            }
            ib, _ := strconv.Atoi(sb)

            if ia < ib {
                return -1
            }

            if ia > ib {
                return 1
            }

            // Windows エクスプローラーの仕様と合わせるために
            // 今回は削除
            // if len(a[ai:aj]) < len(b[bi:bj]) {
            //     return -1
            // }

            // if len(a[ai:aj]) > len(b[bi:bj]) {
            //     return -1
            // }

            // ai = aj
            // bi = bj
        }

        if ca < cb {
            return -1
        }

        if ca > cb {
            return 1
        }

        ai++
        bi++
    }
}

func naturalSort(strings []string) func(i, j int) bool {
    return func(i, j int) bool {
        return natualSort0(strings[i], strings[j]) <= 0
    }
}

func dumpByNaturalSort(strings []string) {
    sort.Slice(strings, naturalSort(strings))
    for i, s := range strings {
        if i != 0 {
            fmt.Print(" < ")
        }
        fmt.Printf("%+v", s)
    }
    fmt.Println()
}

func main() {
    dumpByNaturalSort([]string{"a20", "a10", "a2", "a1b", "a1a", "a1", "a0", "a"})
    // a < a0 < a1 < a1a < a1b < a2 < a10 < a20

    dumpByNaturalSort([]string{"x8-y8", "x2-y08", "x2-y7", "x2-g8"})
    // x2-g8 < x2-y7 < x2-y08 < x8-y8

    dumpByNaturalSort([]string{"1.3", "1.1", "1.02", "1.010", "1.002", "1.001"})
    // 1.001 < 1.1 < 1.002 < 1.02 < 1.3 < 1.010

    dumpByNaturalSort([]string{"001", "01", "1", "10", "010", "2", "002"})
    // 001 < 01 < 1 < 002 < 2 < 010 < 10

    dumpByNaturalSort([]string{"a001", "a01", "a1", "a10", "a010", "a2", "a002"})
    // a001 < a01 < a1 < a002 < a2 < a010 < a10
}

まとめ

自然順ソートでゼロパディングされた数値とそれ以外の数値が混在していたとしても数値順に並ぶようなアルゴリズムを考え、Go言語で実装しました。 しかし、この実装だと、小数点の場合に順番に並んでくれないため、小数点を使うようなソートには向いていません。 ただ、ファイル名等を順番に並べるようなケースでは重宝すると思います。