`sort.Slice` order is undefined

php editor Strawberry will introduce you to some important information about the `sort.Slice` function. In Go language, the `sort.Slice` function is used to sort slices, but the order of its sorted results is undefined. That is, for the same input slice, the results of sorting may be different each time. This is because the `sort.Slice` function uses a fast and efficient sorting algorithm, but the specific order of sorting is based on specific conditions of the input data. Therefore, when using the `sort.Slice` function, we should be aware of the non-determinism of the sorting results to avoid problems in scenarios that rely on a specific sorting order.

Question content

I am trying to sort a string slice using sort.slice from the go standard library. I want them to be sorted alphabetically, except I want the empty string to appear after all other strings (so I can't just use sort.strings).

For the less function, I think this would work:

func(i, j int) bool {
    return s[j] == "" || s[i] < s[j]
}

However, I seem to be getting random answers based on the order of entry. This is mwe:

package main

import (
    "fmt"
    "math/rand"
    "sort"
    "time"
)

func main() {
    s := []string{"", "foo", "bar", "baz"}

    rand.seed(time.now().unix())
    rand.shuffle(len(s), func(i, j int) {
        s[i], s[j] = s[j], s[i]
    })
    fmt.printf("%q\n", s)

    sort.slice(s, func(i, j int) bool {
        return s[j] == "" || s[i] < s[j]
    })
    fmt.printf("%q\n", s)
}

This is the output of running several times:

$ go run ./z
["" "foo" "baz" "bar"]
["bar" "baz" "foo" ""]
$ go run ./z
["baz" "" "foo" "bar"]
["bar" "" "baz" "foo"]
$ go run ./z
["bar" "foo" "" "baz"]
["" "bar" "baz" "foo"]
$ go run ./z
["bar" "foo" "baz" ""]
["" "bar" "baz" "foo"]

Solution

This is because your less() function doesn't say what you want.

You said you want the empty string to be sorted after all non-empty strings. Your logic:

return s[j] == "" || s[i] < s[j]

This does tell us if the second is "", then the first is less. This is more or less true (unless both are empty, "is-less" is not true: they are equal). But what if the first one is "" and the second one isn't? Then your function should return false but it returns s[i] < s[j]. true if the second one is not empty, telling "" to be less than the other, exactly the opposite of what you want.

The correct "is-less" relationship is like this:

sort.slice(s, func(i, j int) bool {
    if s[j] == "" && s[i] != "" {
        return true
    }
    if s[i] == "" && s[j] != "" {
        return false
    }
    return s[i] < s[j]
})

If only the second is "", you want the first to be less. If only the first one is empty, you want it to be "no less than". Otherwise normal order (byte-wise) is used.

Try it on go playground.

Please note that if both the first and second values ​​are empty, this function will return false because "" is not less than "" (They are equal). This is the correct value to return, although returning true here will still result in the correct order (swapping empty elements will result in the same result), but this may result in fewer swaps.

Use xor conversion logic

Please note that in custom logic, if only one string is empty, it will deviate from the normal order. This is logical XOR (XOR) relationship: a xor b is true if only a or only b is true. In go, there is no logical xor operator, but a xor b is equivalent to a != b.

If an empty string is "detected", the result is true if the second empty string is empty (or false otherwise). So we can apply this identity transformation to our logic:

sort.Slice(s, func(i, j int) bool {
    // Move empty elements to the end:
    if (s[i] == "") != (s[j] == "") { // If only one is empty
        return s[j] == ""
    }
    return s[i] < s[j]
})

This is shorter and probably more efficient, but as you can see, it's harder to understand. Use this option only if performance is important. Try this on go playground.

The above is the detailed content of `sort.Slice` order is undefined. For more information, please follow other related articles on the PHP Chinese website!