sorting array of float64

[++pac]

Hi,
does anyone have a code in Go to sort array (like quicksort)? To
prevent me to reinvent wheel ;)

Thanks, Peter.

[Patrick Mylund Nielsen]

package main

import (
"fmt"
"sort"
)

func main() {
fs := []float64{1.3, 1.7, 1.0, 1.9, 1.2}
sort.Float64s(fs)
fmt.Println(fs)
}

# go run sort.go
[1 1.2 1.3 1.7 1.9]

[Patrick Mylund Nielsen]

Sorry. That would be for a slice. Do you actually want to sort an array?

[Vanja Pejovic]

to sort an array would be:

func main() {
       fs := [...]float64{1.3, 1.7, 1.0, 1.9, 1.2}
       sort.Float64s(fs[:])   // fs[:] creates a slices with fs as the backing array
       fmt.Println(fs)

[Patrick Mylund Nielsen]

That was simple!

Btw. Peter, the sort package implements and uses Quicksort.

[Jon Bodner]

After a quick search of the mailing list and the go packages, I didn't
see any code to sort in reverse order. If you need to, you can do
this:

package main

import (
"fmt"
"sort"
)

type ReverseSort struct {
sort.Interface
}

func (r ReverseSort) Less(i,j int) bool {
return !r.Interface.Less(i,j)
}

func main() {
x :=[...]float64{5.4, 3.2, 7.3, 10, -3.1}
sort.Float64s(x[:])
fmt.Println(x)
sort.Sort(ReverseSort{sort.Float64Slice(x[:])})
fmt.Println(x)
}

Note that you use { }, not () when passing a sort.Interface to
ReverseSort.

I'm not a Go expert, but I don't think there's a way to do something
like this with a type conversion only; you need to wrap the interface
reference in a struct to provide an overriding function
implementation.

-jon

On Feb 13, 9:48 am, Patrick Mylund Nielsen <patr...@patrickmylund.com>
wrote:

[John Asmuth]

On Monday, February 13, 2012 5:10:28 PM UTC-5, Jon Bodner wrote:

func (r ReverseSort) Less(i,j int) bool {
        return !r.Interface.Less(i,j)
}

func (r ReverseSort) Less(i,j int) bool { 

        return r.Interface.Less(j, i) 

}  

[Jon Bodner]

Ah, using a function as an intermediary will make the syntax nicer:

package main

import (
"fmt"
"sort"
)

type reverseSort struct {
sort.Interface
}

func (r reverseSort) Less(i,j int) bool {
return r.Interface.Less(j,i)
}

func Reverse(x sort.Interface) sort.Interface {
return reverseSort{x}

}


func main() {
x :=[...]float64{5.4, 3.2, 7.3, 10, -3.1}
sort.Float64s(x[:])
fmt.Println(x)

sort.Sort(Reverse(sort.Float64Slice(x[:])))
fmt.Println(x)
}

-jon

[John Asmuth]

Less(j, i) is not the same as !Less(i, j).

Specifically because now two things that were equal before (Less(i, j) and Less(j, i) were both false) are now inconsistent (!Less(i, j) and !Less(j, i) are both true).

I imagine there are particular sorting algorithms (maybe even whatever is underneath "sort.Sort()") for which this wouldn't be a huge problem, but there are also some for which it would make things go very wrong.

[Jon Bodner]

Yes, after I saw your first post, I realized the mistake. That's why
I switched the implementation of Less in my second example from
negation to permuted parameters.

-jon

[HarrydB]

Wouldn't it be faster (because you don't need the interface
indirection) to sort with sort.Float64s() and then reverse the result?
It is less generic of course.

package main

import (
"fmt"
"sort"
)

func reverseFloat64s(x []float64) {
n := len(x)
for i := 0; i < n / 2; i++ {
j := n - i - 1
x[i], x[j] = x[j], x[i]

}
}

func main() {
fs := []float64{1.3, 1.7, 1.0, 1.9, 1.2}
sort.Float64s(fs)

reverseFloat64s(fs)
fmt.Println(fs)

[Ian Lance Taylor]

HarrydB <ha...@ijscoboer.nl> writes:

> Wouldn't it be faster (because you don't need the interface
> indirection) to sort with sort.Float64s() and then reverse the result?

You get the interface indirection either way. That's how the sort
package works. I would not expect there to be any speed difference.
There is no penalty for converting to a different interface, if that is
what you mean. You get a new method set; it doesn't convert to the old
method set.

Ian

[HarrydB]

On Feb 15, 5:37 pm, Ian Lance Taylor <i...@google.com> wrote:
> You get the interface indirection either way.  That's how the sort
> package works.  I would not expect there to be any speed difference.
> There is no penalty for converting to a different interface, if that is
> what you mean.  You get a new method set; it doesn't convert to the old
> method set.
>
> Ian

Ah of course. Anyway, it is an alternative to get a reverse sort.

Harry

[Vanja Pejovic]

sort.Float64s uses the interface indirection internally.