Why this simple sorting code doesn't work?

[hey...@gmail.com]

Hi,

I have this very simple sorting code:

s := make([]int, 0, 100)
for i := 1; i <= 20; i++ {
    s = append(s, i)
}
sort.Slice(s, func(i, j int) bool { return i > j })
log.Print(s)

I expect it to print numbers in reverse order, since items with larger index numbers should be at the front. However, at lease in go1.19.3, it prints

[9 1 8 5 16 3 20 2 10 7 12 13 14 15 6 4 19 18 17 11]

I guess I must have misunderstood how the sort package works, but rereading sort's doc multiple time doesn't help answer the question.

Could anyone shed some light?

[Andrew Harris]

Subtly:   

     return s[i] > s[j]

Is the right sort func

I think it'd be recommended to look at the generics slices package, which also has a sort

[hey...@gmail.com]

Thanks for the quick reply.

But that seems to compare values. I'd like to compare index numbers. The fact that original values follow index number order is a coincidence.

> I think it'd be recommended to look at the generics slices package, which also has a sort

Do you mean golang.org/x/exp/slices? That also seems to only compare values.

[Eric Hubbard]

sort.Slice(s, func(i, j int) bool { return i > j })

You are comparing the indexes and not the values

-Eric
http://www.google.com/profiles/eric.hubbard

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/47074e6b-b1f2-447e-b7aa-645b9a504913n%40googlegroups.com.

[Andrew Harris]

Oh, to reverse by index ... I think this doesn't quite fit in the idea of sorts defined by an ordering function purely dependent on the value of the element.

I think there may have been a feature request for a `slices.Reverse` function in golang.org/x/exp/slices - I'm not sure what the status or reasoning is on this. FWIW it's not the only approach that might make sense for traversing a slice in reverse order, and it can be naive when working with e.g. bytes holding utf8.

I think this works but I haven't really thought about edge cases...

`reverse(&s)`

func reverse[T any](s *[]T) {
    z := len(*s)
    for a := 0; a < len(*s)/2; a++ {
        (*s)[a], (*s)[z-a-1] = (*s)[z-a-1], (*s)[a]
    }
}

[hey...@gmail.com]

I do want to compare indexes. Is that something possible to do?

In my real code I have other criteria to compare the slice items, but if they tie, I want to use the reverse of their original order.

I expect `return i > j` to put items with larger index numbers at the front, why that doesn't seem to be the case?

[hey...@gmail.com]

> sorts defined by an ordering function purely dependent on the value of the element

Hmm, I thought the function was agnostic to what really get compared? If it offers two index numbers, and the return value says the one with larger index number should be at the front, shouldn't the sort function simply do that, since during the sorting, the passed index number should be stable?

[Robert Engels]

If you compare indexes then the elements are swapped you have messed up the order. 

Imagine the first comparison is 0,15 - you have now swapped those elements - there is no guarantee what order the elements are compared in. 

The index passed in is simply to look up the element. I am supposed this works at all. For example, compare 1,20 - swap - then compare 1,20 again - the sort would expect the inverse Boolean value to be returned - and it won’t be - so your comparison function is not valid/stable. 

You can’t use a sort like this to do what you want. 

On Dec 6, 2022, at 9:28 PM, hey...@gmail.com <hey...@gmail.com> wrote:



--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/5fb85879-b356-4d6d-9645-778d3e7c549an%40googlegroups.com.

[Andrew Harris]

Just as an intuitive argument, we could do:

sort.Slice(s, func(i, j int) bool { log.Println(i, j); return i > j })

The appearances of i and j per step recapitulate the logic of the sorting algo in some weak sense; not slice order

[Andrew Harris]

> In my real code I have other criteria to compare the slice items, but if they tie, I want to use the reverse of their original order.

Oh, forgot to say: FWIW - I think reversing and then sort.SliceStable might be a solution - asymptotically reverse should be less complex than the sort, or probably there are other variations that don't require reimplementing sorting.

[hey...@gmail.com]

Reversing and then using the stable sort sounds like an elegant solution. Thanks!

@Robert

I totally missed the indexes could refer to swapped items. I somehow had the impression that go would memorize the returned order and swap them in one go. This explains it. Thanks a lot.

[Daniel Lepage]

On Tue, Dec 6, 2022 at 10:29 PM hey...@gmail.com <hey...@gmail.com> wrote:

> sorts defined by an ordering function purely dependent on the value of the element

Hmm, I thought the function was agnostic to what really get compared? If it offers two index numbers, and the return value says the one with larger index number should be at the front, shouldn't the sort function simply do that, since during the sorting, the passed index number should be stable?

This is almost correct, except that the slice is sorted in-place so the index numbers aren't actually stable.

The i and j passed into the function should be used solely to look up elements in the array. I suspect that in most use cases, it would be more helpful to have a function 

sort.Slice[T any](x []T, less func(a, b T) bool)

i.e. the sort function would take two values read from the list instead of two indices, to avoid exactly this sort of confusion, but A) it was written before generics, and B) in the particular case of []struct{...}, two structs get copied for each call to less().

-- 

Dan