5
\$\begingroup\$

I have implemented a HTML table sorting. I actually implemented a sort first using jQuery and then modified it based on the answer to this question for performance as I had done the same mistake. My question is how to make sure if the code I have written is stable or not?

I know that the stability of sorting depends on the sort method's algorithm and that changes with the browser, and according to this page, mozilla's implementation of sorting is stable, but when I checked with my code, it doesn't seem to be stable. Could someone have a look at my code and let me know how to determine whether the sort performed is stable or not?

<html><head>
        <script src="http://ajax.googleapis.com/ajax/libs/jquery/1.10.2/jquery.min.js"></script>
        <script type="text/javascript">
        $(document).ready(function(){
        asc = new Array();
        for (var a=0;a<$("tbody tr:eq(0) td").length;a++) asc[a] = 1;
    $("th").click(
    function(){
        c = $(this).index();
        var rows = $("tbody tr");
        var rlen = rows.length;
        var arr = new Array();
        var cols;
        for(var i=0;i<rlen;i++){
            cols = $("tbody tr:eq("+i+") td");
            var clen = cols.length;
            arr[i] = new Array();
            for (var j=0;j<clen;j++){
                arr[i][j] = $("tbody tr:eq("+i+") td:eq("+j+")").html();
            }
        }
        arr.sort(function(a,b){
            if (a[c]==b[c]) return 0;
            else if(a[c]<b[c]) return -1 * asc[c];
            else return asc[c];
        });
        for (var i=0;i<rlen;i++){
            arr[i] = "<td>" + arr[i].join("</td><td>") + "</td>"
        }
        $("tbody").html("<tr>"+arr.join("</tr><tr>")+"</tr>");
        asc[c] = (asc[c]==1)?-1:1;
    });});
        </script>
        <style type="text/css">
        table { border-collapse: collapse; border: none;}
        th,
        td {
            border: 1px solid black;
            padding: 4px 16px;
            font-family: Times New Roman;
            font-size: 24px;
            text-align: left;
        }
        th {
            background-color: #D8D8D8;
            cursor: pointer;
        }
    </style>
    </head><body>
        <table>
            <thead>
                <tr>
                    <th>Month</th>
                    <th>Savings</th>
                </tr>
            </thead>
            <tbody>
                <tr>
                    <td>March</td>
                    <td>180</td>
                </tr>
                <tr>
                    <td>January</td>
                    <td>100</td>
                </tr>
                <tr>
                    <td>February</td>
                    <td>80</td>
                </tr>
                <tr>
                    <td>Januray</td>
                    <td>40</td>
                </tr>
                <tr>
                    <td>March</td>
                    <td>200</td>
                </tr>
                <tr>
                    <td>February</td>
                    <td>90</td>
                </tr>
            </tbody>
        </table> 
    </body></html>

And if there can be any improvements for efficiency, can anyone point that out as well?

\$\endgroup\$

2 Answers 2

Reset to default
3
\$\begingroup\$

From a once over;

  • The easiest way to be sure that you sort algorithm is stable, is to write you own sort algorithm.
  • The second easiest way to be sure is to pass in each array entry object it's position in the array ( you could set this after your arr[i][j] assignment ). If (a[c]==b[c]) then you would not return 0, but you would return -1 or +1 based on their original position in the array
  • You did not declare c and asc with var
  • var arr = []; is preferred to var arr = new Array();
  • One single comma separated var statement is preferred over many var statements
  • You declare var i twice, since var i declares i for the scope of the function, you do not need to declare it again.
  • Your indenting is off, you should look into that
  • Assigning a function to document.ready is old skool, you should look into using addEventListener or simple using $( handler );.

  • You should cache the value of a<$("tbody tr:eq(0) td").length

     for (var a = 0, count = $("tbody tr:eq(0) td").length; a < count ; a++)

  • On my second point, imagine you are sorting people by their age, in a stable manner:

Bob, 23 years John, 12 years Tricia, 23 years

becomes

Bob, 23 years Tricia, 23 years John, 12 years

it would be unstable if the order was

Tricia, 23 years Bob, 23 years John, 12 years

because Tricia was initially below Bob, she should stay below Bob. You can accomplish this by comparing the original position of the 2 records and making sure that if the age is the same, you make sure the original order is respected.

I hope this example made it clearer.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the answer konijn, I implement my own sorting algorithm to ensure stability, but I did not understand your second point. Could you please explain that a bit more? \$\endgroup\$
    – anirudh
    Commented Apr 1, 2014 at 7:53
  • \$\begingroup\$ Thanks again for the explanation, it definitely made it a lot clearer... \$\endgroup\$
    – anirudh
    Commented Apr 1, 2014 at 15:41
1
\$\begingroup\$

Additionally to what @konijn wrote:

Instead of "reselecting" the rows/cells in your first loop, use the already selected items. Also use the child selector (>)

var rows = $("tbody > tr"),
    rlen = rows.length,
    arr = [];
for (var i = 0; i < rlen; i++){
     var cols = rows.eq(i).find("> td");
     var clen = cols.length;
     arr[i] = [];
     for (var j = 0; j < clen; j++){
         arr[i][j] = cols.eq(j).html();
     }
}

Also instead of rebuilding the whole table, consider storing references to each row with the data and just re-append all existing rows in the correct order.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.