sorting - How can I sort this "matrix" of data? -

i run sporting website, , it's useful rank people against each other based on previous meetings.

see example set of data:

on left raw "unsorted" view. on right correctly sorted (in opinion) list.

each square shows number of times they've competed against each other, , percentage of victories. they're shaded based on percentage.

i have in webpage, "up" , "down" controls alongside each row, , can manually nudge them around until want.

i'm not quite sure of best way automate this.

the numbers @ end of each row quick idea roughed out, , equal sum across row of (percentage-50 * column number). can see, job, first 2 rows being "wrong". don't give weight number of meetings though, win percentage.

the final-column numbers change depending on row order well, can seen comparing left , right tables in image, sorting on initial values wouldn't work well. looping sort + re-calc couple of times might job.

i expect can cobble make work... feel have much better ideas, , i'm ears.

a tournament graph in there 1 directed edge between every pair of vertices; create such graph input, make graph vertex each player, , "point" each edge between 2 players in direction of player won majority of games (you need break ties somehow).

if this, , if there no cycles > b > ... > of type mentioned in comment in graph, graph transitive, , can order players using topological sort of graph. takes linear time in number of edges, i.e. o(n^2) n players.

if there are such cycles, there's no "perfect" ordering of players: ordering place @ least 1 player after player have beaten. in case, reasonable alternative orderings minimise number of these "edge violations". turns out well-studied np-hard problem in computer science called (minimum) feedback arc set in tournaments (fast). feedback arc set set of directed edges ("arcs") which, if deleted graph, leave graph no directed cycles -- can turned order using topological sort before.

this paper describes recent attack on problem. haven't read paper, active area of research , algorithm quite complicated -- might give ideas how create simpler algorithm runs slower (but acceptably fast on such small instances), or how create heuristic.