How to verify if HTML table sort is stable or not?

Question 1

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?

Question 2

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.

Question 3

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.

Leave a Reply Cancel reply