sort.Sort random output and is wrong

[Sathish VJ]

I have a custom Sort function applied to a struct. The full code is here on play.golang.org.

My purpose is to automatically create a set of sql create statements ordered properly so that dependent tables come first.

So if Stmt{Name: "user_role", After: []string{"user", "role"} } is present, then in the ordered list user_role should be after both user and role.

This seemed to work fine for a bit until we started adding more values. Only then did I go in and check and realize that I might have just got accidentally lucky the first time, but there really isn't any consistency.

type Stmt struct {



 Name  string

 After []string

}




func sortStmts(stmts []Stmt) []Stmt {

 sort.Sort(ByAfter(stmts))

 return stmts

}




type ByAfter []Stmt




func (a ByAfter) Len() int      { return len(a) }

func (a ByAfter) Swap(i, j int) { a[i], a[j] = a[j], a[i] }

func (a ByAfter) Less(i, j int) bool {

 isLess := true




 //fmt.Printf("%s.%+v is being compared with %s.%+v\n", a[i].Name, a[i].After, a[j].Name, a[j].After)




 for _, v := range a[i].After {

 if a[j].Name == v {

 isLess = false

 break

 }

 }




 if isLess {

 //fmt.Printf("%s.%+v is Before %s.%+v\n", a[i].Name, a[i].After, a[j].Name, a[j].After)

 } else {

 //fmt.Printf("%s.%+v is After %s.%+v\n", a[i].Name, a[i].After, a[j].Name, a[j].After)

 }




 return isLess

}

Is there something I'm doing wrong in the sort function that the results are random. I'm particularly interested in seeing why the "role" item is not coming before the "user_role" item even though I've designated it user_role as coming after role.

I posted the same qn on SO also (http://stackoverflow.com/questions/29025460/golang-sort-sort-random-output-and-is-wrong).

[David DENG]

I think the problem is the Less implemented is not a correct order function, i.e. for any a < b, b < c =/=> a < c.

What you need is a topological sorting, it's not done by a normal sorting with a special comparator.

David

[Sathish VJ]

In my case, I did check and there is that transitive nature in the dependencies.  

One specific thing I'm noting when I print out the debug statements is that some comparisons are never happening.  For example, user_role is never getting compared to role as of now.  Though at one point when there were lesser elements, it was.  

Does that have anything to do with the transitive nature of the sort used?

[Dan Kortschak]

Since I had a tarjan lying around. Here is the topological sort for that
data:

http://play.golang.org/p/SHagFMvuhl

On Thu, 2015-03-12 at 22:47 -0700, Sathish VJ wrote:
> In my case, I did check and there is that transitive nature in the
> dependencies.
>
> One specific thing I'm noting when I print out the debug statements is
> that some comparisons are never happening. For example, user_role is
> never getting compared to role as of now. Though at one point when
> there were lesser elements, it was.

sort.Sort will not make all comparisons. That would result in O(n^2)
time.

[Sathish VJ]

Thank you for your answers.  

@kortschak, could you please add your response on stackoverflow also (http://stackoverflow.com/questions/29025460/golang-sort-sort-random-output-and-is-wrong) just so that it is more accessible for others also.