• Post Reply Bookmark Topic Watch Topic
  • New Topic

sorting a 2d array  RSS feed

 
luc comeau
Ranch Hand
Posts: 97
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey people,

I am in a little situation here, and maybe its because im stressed but i cant think of a nice way to sort this 2d array i have.

Details: the 2d array is an array of probabilities between {0,1}.say i have the matrix,where the vertical axis is called y,horizontal called x.
\x
y| 0, 1, 1 , 1
0, 0, .8, 0.4
0, 0, 0 , 0.45
0, 0, 0 , 0
the probabilities are that yi is preffered over xj. example, the 0.8 is that
Prob(y1>x2)----prob that y1 preffered over x2 is 0.8.

now each row and column position corresponds to a unique offer thats why there are 0's in all positions where i=j.

So for this example there are 4 elements, i need to figure out the overall ordering of those elements based on these probabilities.I do a comparision where 0.5 is the cut off for saying something is preffered over the other.

So for this example obviusly we know that y0>x1, yo>x2, y0>x3 and y1>x2, y1!>x3...and so on.

I hope i haven't lost you yet, because my true question is i need an algorithm that, based on this array, will spit out the correct ordering at the end, based on all the conditions present in the matrix. Note that these matricies will be well formed so there will be no conflicts in the data.

The algorithm in this example should produce:0>3>1>2, based on the matrix values.
Im not sure whether to approach this with recursion and whther to sort inplace or what, its proving to be more difficult then i imagined. Please if you are at all confused, ask me questions its really not quite as difficult as i may have described it. bare bones its a sorting problem. Any help or tips on this would be great, thanks so much rancher's

Luc
 
luc comeau
Ranch Hand
Posts: 97
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
im thinking about doing somthing where, for each row, i look and see if there are any probs<0.5 if that number is less than 0.5 add it to an array for that row, if it is greater then 0.5, add the pos of the row to the array for the colum pos. At the end do a topological sort, check to see which array has no elements, then for that one go through the rest of the arrays and delete that one from the rest of them, loop through this until all are empty and i think i should come out with the correct ordering...hopefullly, asuming that my matrix is Asyclic directional not cyclic directional

Anyways im going to try my hand at programming this, ill keep a post of how its going maybe someone still has a better idea?
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!