JavaScript Algorithms – Efficient Algorithm to Sort HTML List of Players

Well I hope, I'll answer all your questions and be precise enough.

The answer to all your questions is yes, it is possible to do all of that in Javascript:

What kind of task it is? Just sort?

You have to sort data, but you also have to update some data (points, name?, position) and display it to the user.

Is it ok to use JavaScript to solve this task if lists are less than 500 rows?

You can rearrange tables composed of 500 rows with JavaScript, no problem (using a bit of JQuery), and I don't think you would have any performance trouble with that. The only problem you could have is if you attempt to animate 500 moving rows (more on that later)

Is it ok to re-render whole players list, or there are some ways to just change div element position(index in DOM or something like this)?

Well, I think it is ok to re-render the whole players list, but if you do that, how will perform position-change animations ?

Are there any tools and libraries around, that can help solve this task efficiently?

Obvious answer: JQuery and JQuery UI (or your favorite JavaScript framework for performing animations)

If we want to animate all this story - we should create a queue of animation tasks each time scores for all players recalculates?

I think you should perform the animations one by one after you know the final position of each player. Otherwise, you could perform animations when nothing has changed (player3 may move from 3 to 1, then player2 moves from 2 to 1, then player1 moves from 1 to ... 1, nothing has changed!)

DOM only vs DOM backed by a JSON Data Model

Now, regardless of the tools, or algorithm you are going to use, if you work only with DOM elements, without having a "backend" JSON data model (please someone complete here if you see more problems):

• Finding the new position of a given player will be a pain
• Updating the positions of every player will be a pain

If you work with DOM elements for rendering, backed by a JSON data model, and provided you make the following changes to your individual player display, you will have a much easier time:

   <div class="player" id="player2">
        <div class="name">Player2</div>
        <div class="points" id="playerPoints2">400</div>
        <div class="position" id="playerPosition2">2</div>
   </div>

• Notice that I've added an id attribute to the player <div> and to the elements displaying the points ("playerPoints2") and the position ("playerPosition2"). Doing that will allow you to quickly find the position of a player or its points, given its unique id. You could do without, but that would affect performance and you would have to use more complex queries (see JQuery's .find())

My attempt:

In short, what I try to do is moving as few DOM elements as possible, and decorrelating the data from the display.

Imagine having the following JSON data model in addition to your DOM model for displaying the players:

• player (array of players)
  • id
  • position (you can write a custom function for sorting the array given the "position" attribute if each item of the array)
  • points
  • name

and the following JSON data model for performing animations later:

• playerChanges (array of player changes)
  • id
  • deltaPosition (example: +3 = 3 ranks higher than before) . * isComputed (boolean)

After receiving data from the server, here's what I would do:

• sort the list of backend players, given their respective position. The first element of the array should be the top ranked player.
• loop over the data received from the server
• if the points of a player change, then:
  • look up the player in the array
  • update its points
  • move the player to the position in the array where it should fit, but don't change the "position" attribute
  • create a new entry in the "playerChanges" array, storing only the id of the player (we will compute the delta only at the end)
• loop on the array of backend players, and for each player in "playerChanges" (this is important) that is nit yet conputed, compute the position attribute regarding to the position of the player in the array. Since you have his "old" position, and the position in the array, you can compute the "deltaPosition". Edit: after you compute the delta, mark the "playerChange" as computed and restart looping on the array of backend players. Do that as long as there is an uncomputed ""playerChange"" in the array.

In the end you should have an array of "playerChanges". This is the list of rows that you should move, given the "deltaPosition" of each player. Notice that it could be 0, which means that the player received new points, but his position did not change. To perform the animation, I would suggest looking at this brilliant answer.

After you have done these animations, you can loop again on the list of backend players in order to update the displayed position ("playerPositionXXX" where XXX is the id of the player) of each player.

What I've attempted to do here is to decorrelate the "update and sort" from what happens on the screen, the animation that the user sees.

Edit: here is a working code sample (on Chrome at least) of an animation with JQuery and JQueryUI.

<html>
    <head>
        <title>Temp test</title>
        <script src="http://ajax.googleapis.com/ajax/libs/jquery/1.8.0/jquery.min.js"></script>
        <script src="http://ajax.googleapis.com/ajax/libs/jqueryui/1.8.23/jquery-ui.min.js"></script>
        <style type="text/css">
            * { font-family: Calibri;}
            .player { border: 1px solid grey; background: #f0f0f0; width: 300px; 
                        padding: 10px; margin-bottom: 5px; margin-top: 5px; }
                .name { margin-left: 30px; font-size: 20px; font-weight: bold; }
                .points { float: right; color: whitesmoke; font-size: 24px; font-weight: bold; margin-top: -30px; 
                            background-color: #999; padding: 3px;}
                .position { clear: both; display: block; float: left; 
                            font-size: 20px; font-weight: bold; margin-top: -29px; padding-right: 10px; 
                            border-right: 1px solid black;}
        </style>
        <script type="text/javascript">

            function movePlayer(playerToMoveId, delta) {
                var $old = $(playerToMoveId);
                var $new = $old.clone();

                // TODO: here I don't take into account the delta
                // 
                // you need to write a simple method for determining the player
                // that will be replaced (here I hardcoded "p4"). 
                $("#p4").before($new);

                var newOffset = $new.offset();
                //Get the old position relative to document
                var oldOffset = $old.offset();
                //we also clone old to the document for the animation
                var $temp = $old.clone().appendTo('body');
                //hide new and old and move $temp to position
                //also big z-index, make sure to edit this to something that works with the page
                $temp
                  .css('position', 'absolute')
                  .css('left', oldOffset.left)
                  .css('top', oldOffset.top)
                  .css('zIndex', 1000);
                $new.hide();
                $old.hide();
                //animate the $temp to the position of the new img
                $temp.animate( {'top': newOffset.top, 'left':newOffset.left}, 'slow', function(){
                   //callback function, we remove $old and $temp and show $new
                   $new.show();
                   $old.remove();
                   $temp.remove();
                });
            }
        </script>
    </head>
    <body>
        <div class="players_list" id="plist">
           <div class="player" id ="p4">
                <div class="name" id="pName4">Player4</div>
                <div class="points" id="pPts4">800</div>
                <div class="position" id="pPos4">1</div>
           </div>
           <div class="player" id="p3">
                <div class="name" id="pName3">Player3</div>
                <div class="points" id="pPts3">500</div>
                <div class="position" id="pPos3">2</div>
           </div>

           <div class="player" id="p1">
                <div class="name" id="pName1">Player1</div>
                <div class="points" id="pPts1">300</div>
                <div class="position" id="pPos1">3</div>
           </div>     
           <div class="player" id="p2">
                <div class="name" id="pName2">Player2</div>
                <div class="points" id="pPts2">250</div>
                <div class="position" id="pPos2">4</div>
           </div>
        </div> 

        <input type="button" onclick="movePlayer($('#p2'), 3)" value="Animate"/>
    </body>
</html>