A 'Sorting' Puzzle

[Mel Smith]

Hi:

Background:
I have an online phonebook which is in a <table> element of two
columns. There are 613 cells arranged (of course) in two columns. The 'sort'
is left and right, then downwards to the bottom of the table The table is
sorted alphabetically by surname

Question:
I'm asked by the manager of my Senior Park if I can change the sort to
'Phone Number', or Lot No., etc.

This data appear in each cell.

Is there a way to do this different 'sorts' in situ ?

Thanks,

 

[Mel Smith]

Question:

I'm asked by the manager of my Senior Park if I can change the sort to
'Phone Number', or Lot No., etc.

Hi:

That's a bad question. I'm sorry.

But, maybe I can re-phrase it in the following way:

Question:

Can the cells in a 2-column table of 307 rows be re-sorted in situ
(i.e., by javascript), based on data within each cell where that data is
always in a certain line and position within that line. ?

Note, each cell contains four lines of information (among thos four
lines is info about surname, fname, local phone number , address, etc)

If so, I'll start my brain busting. If not, I've got to go back to the
server (maybe with XHR ??) and re-build the table for the user.

Thank you (again).

 

[Ross McKay]

I have an online phonebook which is in a <table> element of two
columns. There are 613 cells arranged (of course) in two columns. The 'sort'
is left and right, then downwards to the bottom of the table The table is
sorted alphabetically by surname
[...]
Is there a way to do this different 'sorts' in situ ?

http://duckduckgo.com/?q=sort+table+javascript


--
Ross McKay, Toronto, NSW Australia
"The documentation and sample application having failed me,
I resort to thinking. This desperate tactic works, and I
resolve that problem and go on to the next"
- Michael Swaine, "Programming Paradigms", Dr Dobb's Journal

 

[RobG]

Hi:

    That's a bad question. I'm sorry.

    But, maybe I can re-phrase it in the following way:

Question:

    Can the cells in a 2-column table of 307 rows be re-sorted in situ
(i.e., by javascript), based on data within each cell  where that data is
always in a certain line and position within that line. ?

The usual strategy goes along the lines of: create an object, iterate
over the rows of the table and add properties to the object that are
the text to be sorted on and whose value is a reference to the
containing table row.

The property names are also added to an array that is sorted according
to whatever algorithm is suitable. Then iterate over the sorted array,
using the members as keys to put the rows in the correct order in the
table by simply appending them to the related tbody element. The rows
are moved, which is quite quick.

    Note, each cell contains four lines of information (among thos four
lines is info about surname, fname, local phone number , address, etc)

How you decide to process the cell contents to get the key to sort on
is up to you.

Here's a quick exmaple to show the method, note there is zero feature
testing or checking so it's not for production. The listener should be
on the table itself rather than on each column and have support for
forward and reverse sorting, sort by alpha or number or date and so
on. The getText and trim functions are also built for brevity not for
robustness.


<script type="text/javascript">
function getText(el) {
return (typeof el.textContent == 'string')?
el.textContent : el.innerText
}

function trim(s) {
return s.replace(/^\s*|\s*$/g,'');
}

function tableSort(el) {
// Ref to parent table
var table = el.parentNode.parentNode.parentNode;
// Column of cell clicked on
var idx = el.cellIndex;
var body = table.getElementsByTagName('tbody')[0];
var row, rows = body.rows;
var cell, nbody, value;
var o = {};
var a = [];

// Extract the text to be sorted and remember
// related row
for (var i=0, iLen=rows.length; i<iLen; i++) {
row = rows
value = trim(getText(row.cells[idx]));
a.push(value);
o[value] = row;
}

// Sort
a.sort()

// Rebuild table
// Old IE barfs when moving rows using existing tbody
// so use a new tbody
nbody = body.cloneNode(false);

for (var k=0; k<iLen; k++) {
value = a[k];
nbody.appendChild(o[value]);
}
table.replaceChild(nbody, body);
}
</script>

<table id="t0">
<thead>
<tr>
<th onclick="tableSort(this);">Index
<th onclick="tableSort(this);">Name
<th onclick="tableSort(this);">DoB
</thead>
<tbody>
<tr><td>1<td>Fred<td>1986-01-15
<tr><td>2<td>Vivian<td>1957-12-04
<tr><td>3<td>Sally<td>1956-03-17
</tbody>
</table>

 

[Denis McMahon]

Question:

Can the cells in a 2-column table of 307 rows be re-sorted in situ
(i.e., by javascript), based on data within each cell where that data is
always in a certain line and position within that line. ?

Note, each cell contains four lines of information (among thos four
lines is info about surname, fname, local phone number , address, etc)

If so, I'll start my brain busting. If not, I've got to go back to the
server (maybe with XHR ??) and re-build the table for the user.

Can you produce an example table with a few rows of dummy data in it?

Perhaps with misters schmidt, smith, jones and doe in it, showing how
your data is laid out in the table.

Then we can see what needs to be done to sort it.

I've been playing about with dynamically re-ordering table contents
using the dom recently, but haven't actually tried reading a table into
sortable objects from the dom, rather I generate an array for the
javascript to work with from the server and then use an onload to
initially generate the table. However, I'd be interested in looking at
your problem as an exercise in "doing it if it can be done" regardless
of whether it's the best way to do it or not.

Rgds

Denis McMahon

 

[Mel Smith]

Rob said:
The usual strategy goes along the lines of: create an object, iterate
over the rows of the table and add properties to the object that are
the text to be sorted on and whose value is a reference to the
containing table row.

The property names are also added to an array that is sorted according
to whatever algorithm is suitable. Then iterate over the sorted array,
using the members as keys to put the rows in the correct order in the
table by simply appending them to the related tbody element. The rows
are moved, which is quite quick.

Note, each cell contains four lines of information (among thos four
lines is info about surname, fname, local phone number , address, etc)

How you decide to process the cell contents to get the key to sort on
is up to you.

Here's a quick exmaple to show the method, note there is zero feature
testing or checking so it's not for production. The listener should be
on the table itself rather than on each column and have support for
forward and reverse sorting, sort by alpha or number or date and so
on. The getText and trim functions are also built for brevity not for
robustness.

Rob:

Thanks for the guide and example. I'll copy it and take it to bed with
me !

-Mel

 

[Mel Smith]

Denis said:

Can you produce an example table with a few rows of dummy data in it?

Perhaps with misters schmidt, smith, jones and doe in it, showing how
your data is laid out in the table.

Then we can see what needs to be done to sort it.

Yes, I'll try to get a table operational in my whosaway.com website
tomorrow sometime to give you folks an idea.

(But, I have the Manager of our Senior's Park visiting tomorrow to look
at this stuff I'm doing, and I have to get ready for her first. -- but
*yes*, I'll get something out there for you later tomorrow. (But, they are
very sensitive in my Park about letting phone numbers loose over the
internet -- paranoid older people like me)

I've been playing about with dynamically re-ordering table contents
using the dom recently, but haven't actually tried reading a table into
sortable objects from the dom, rather I generate an array for the
javascript to work with from the server and then use an onload to
initially generate the table. However, I'd be interested in looking at
your problem as an exercise in "doing it if it can be done" regardless
of whether it's the best way to do it or not.

Thanks Denis -- I'll do it later tomorrow.

 

[Mel Smith]

"> http://duckduckgo.com/?q=sort+table+javascript

Ross:

Thanks for the link.

 

[Lasse Reichstein Nielsen]

Hi:

That's a bad question. I'm sorry.

But, maybe I can re-phrase it in the following way:

Question:

Can the cells in a 2-column table of 307 rows be re-sorted in situ
(i.e., by javascript), based on data within each cell where that data is
always in a certain line and position within that line. ?

Sure you can. You can do ANYTHING

Note, each cell contains four lines of information (among thos four
lines is info about surname, fname, local phone number , address, etc)

You'll have to find a way to extract the phone number in order to search
for it. You should be able to do that fairly easily.
Always on the same line (say line four) of the first cell of the row?
function extractKey(row) {
return row.cells[0].innerHTML.split("\n")[3];
}

If so, I'll start my brain busting. If not, I've got to go back to the
server (maybe with XHR ??) and re-build the table for the user.

I'd use a function like this:

// Takes a table element, a function from row to key,
// and a comparison function.
function tableSort(table, extractKey, compareFn) {
// Hide the table to reduce reflows during operation.
table.style.display = "none";
// Extract the rows and keys from rows.
var rows = [];
for (var i = table.tBodies.length - 1; i >= 0; i--) {
var tbody = table.tBodies;
for (var j = tbody.rows.length - 1; j >= 0; j--) {
var row = tbody.rows[j];
tbody.removeChild(row);
rows.push(new SortEntry(row, extractKey(row)));
}
}
// Sort.
rows.sort(compareFn);
// Reinsert.
var firstBody = table.tBodies[0];
for(var i = 0; i < rows.length; i++) {
firstBody.appendChild(rows.row);
}
// Reset table display.
table.style.display = "";
}

function SortEntry(row, key) {
this.row = row;
this.key = key;
}
// In case you want to use the default compare function, which
// converts everything to string.
SortEntry.prototype.toString = function() { return this.key; };


Best of luck
/L

 

[Denis McMahon]

Denis said:


Yes, I'll try to get a table operational in my whosaway.com website
tomorrow sometime to give you folks an idea.

(But, I have the Manager of our Senior's Park visiting tomorrow to look
at this stuff I'm doing, and I have to get ready for her first. -- but
*yes*, I'll get something out there for you later tomorrow. (But, they are
very sensitive in my Park about letting phone numbers loose over the
internet -- paranoid older people like me)

It doesn't have to be real data, but it does need to show the exact
formatting and layout of the real data.

It only needs a few table rows, in reality one would suffice, plus the
table header (and footer if any) but three or four would be better.

Also, are you generating the table dynamically from a database?

Rgds

Denis McMahon

 

[Mel Smith]

Lasse said:

Sure you can. You can do ANYTHING


You'll have to find a way to extract the phone number in order to search
for it. You should be able to do that fairly easily.
Always on the same line (say line four) of the first cell of the row?
function extractKey(row) {
return row.cells[0].innerHTML.split("\n")[3];
}


I'd use a function like this:

// Takes a table element, a function from row to key,
// and a comparison function.
function tableSort(table, extractKey, compareFn) {
// Hide the table to reduce reflows during operation.
table.style.display = "none";
// Extract the rows and keys from rows.
var rows = [];
for (var i = table.tBodies.length - 1; i >= 0; i--) {
var tbody = table.tBodies;
for (var j = tbody.rows.length - 1; j >= 0; j--) {
var row = tbody.rows[j];
tbody.removeChild(row);
rows.push(new SortEntry(row, extractKey(row)));
}
}
// Sort.
rows.sort(compareFn);
// Reinsert.
var firstBody = table.tBodies[0];
for(var i = 0; i < rows.length; i++) {
firstBody.appendChild(rows.row);
}
// Reset table display.
table.style.display = "";
}

function SortEntry(row, key) {
this.row = row;
this.key = key;
}
// In case you want to use the default compare function, which
// converts everything to string.
SortEntry.prototype.toString = function() { return this.key; };

Lasse:

Thanks for your suggestions and examples. I'll start work on it later
today.

-Mel

 

[Mel Smith]

Denis said:

Can you produce an example table with a few rows of dummy data in it?

Perhaps with misters schmidt, smith, jones and doe in it, showing how
your data is laid out in the table.

Then we can see what needs to be done to sort it.

I've been playing about with dynamically re-ordering table contents
using the dom recently, but haven't actually tried reading a table into
sortable objects from the dom, rather I generate an array for the
javascript to work with from the server and then use an onload to
initially generate the table. However, I'd be interested in looking at
your problem as an exercise in "doing it if it can be done" regardless
of whether it's the best way to do it or not.

Hi Denis:

I've stripped down the table to its essentials, and have only four or
five rows, and the data is obscured with phony names, and numbers

The actual table has 307 'rows' of informatron with two residents per
row.

Please visit www.whosaway.com and enter the Password: MEP to see this
short artificial table

Thank you.

-Mel Smith

 

[Denis McMahon]

Please visit www.whosaway.com and enter the Password: MEP to see this
short artificial table

Hi

I did it with javascript, it works on the example data, and there are 4
sort options:

Either "Name" or "Lot number" and "ascending" or "descending"

http://www.sined.co.uk/tmp/jstablesort.htm

There are a few changes to the html and css as well as all the
javascript, I think I've added comments showing the changes but in summary:

css - moved the listing div down to make space for the sort buttons
html - added a function call to the body element's onload attribute,
added a paragraph containg 4 new buttons after the "listings" id div,
added an id attribute to the table.

How it works:

When the document has loaded, the onload attribute of the body element
calls a javascript routine which attempts to parse the table and extract
data records (it actually extracts the innerHTML of the table cells)
from which it tries to also obtain a name and a lot number.

An assumption is that the left side of the table will always contain a
valid record, but the right side might contain padding if the number of
entries in the table is odd - but I don't know if the code I've used to
detect a blank record will work with whatever your code generates as
filler space.

When you click the sort buttons, the data is sorted using custom sort
functions, which will (hopefully) do the required sort and ensure that
any blank record that was inserted in the table to even up the numbers
appears as the last record.

After the data has been sorted, the existing table rows are deleted and
the table is recreated using the sorted data.

Rgds

Denis McMahon

 

[Dr J R Stockton]

Can the cells in a 2-column table of 307 rows be re-sorted in situ
(i.e., by javascript), based on data within each cell where that data is
always in a certain line and position within that line. ?

Rows and columns of tables, although indexable, are not arrays, and have
no sort method.

Since the elements can be both read and written, all normal sort
algorithms (which does not imply sort methods) can be programmed to work
on tables in situ.

I have an instinctive feeling that handling table elements may be slower
than handling elements of a corresponding array. If speed matters,
check that.

The built-in sort method is likely to be faster than a home-brew, if
given a well-considered sort function or if not needing one.

If you have to sore something unhelpful, such as US-format date strings
or dates containing letters, every comparison will need two of those to
be rendered comparable, and sorting tends to take N log N or more
comparisons. Therefore, in such cases, do a preliminary pass to
generate directly comparable sort keys.

Assume that rows are to be stable, and sorted into the order of a
particular column. I think that if you represent the entire structure
as an array of rows, with the rows being arrays, with the zero element
of a row holding the sort key, and the rest of the array holding the
table data however convenient, then you can use the built-in sort after
setting the keys to suit the order desired.

The art of sorting lies in not moving the actual data, just adjusting
what are in effect pointers. That's easy in JavaScript.

Be aware that there is no need to sort on demand. The page can be
fetched containing, for example, an "2-D" array of rows, and other
simple arrays indexing the data in all orders on offer. Then, when the
user "demands" a sort, just write the table in the desired order using
the appropriate one of those arrays.

If the user can input data, so that it cannot all be pre-sorted at
download, you can insert a pointer to the new data at the right position
of each list while the user is looking for the next data line.

You can also sort all the downloaded data in JavaScript onload, with the
sort buttons temporarily disabled, distracting the user until the
buttons can be enabled,

<http://www.merlyn.demon.co.uk/js-order.htm> might help.

 

[Mel Smith]

Denis:

I did it with javascript, it works on the example data, and there are 4
sort options:

Either "Name" or "Lot number" and "ascending" or "descending"

http://www.sined.co.uk/tmp/jstablesort.htm

There are a few changes to the html and css as well as all the
javascript, I think I've added comments showing the changes but in
summary:

css - moved the listing div down to make space for the sort buttons
html - added a function call to the body element's onload attribute,
added a paragraph containg 4 new buttons after the "listings" id div,
added an id attribute to the table.

How it works:

When the document has loaded, the onload attribute of the body element
calls a javascript routine which attempts to parse the table and extract
data records (it actually extracts the innerHTML of the table cells)
from which it tries to also obtain a name and a lot number.

An assumption is that the left side of the table will always contain a
valid record, but the right side might contain padding if the number of
entries in the table is odd - but I don't know if the code I've used to
detect a blank record will work with whatever your code generates as
filler space.

When you click the sort buttons, the data is sorted using custom sort
functions, which will (hopefully) do the required sort and ensure that
any blank record that was inserted in the table to even up the numbers
appears as the last record.

After the data has been sorted, the existing table rows are deleted and
the table is recreated using the sorted data.

Denis:

Wow !!! -- what a fast great job !

I'll look it over and follow your guidance .

Thanks a million !

Mel Smith
Mesa, Arizona

 

[Mel Smith]

Hi Denis:

I modified your example by inserting all your functions, and ensuring
the last (unoccupied) element had a Lot 999 in it plus (as the Name): [NO
LOT], then I ran it and it sorted perfectly !!

Thank you.

The sort for each of the parameters took approx 20 seconds on my P5
machine. Maybe I should warn the user to 'sit back and relax' for a few
moments while the new table building is progressing )

Thanks again for this fast, perfect work (I'm jealous of your experience and
speed )

-Mel Smith

 

[Mel Smith]

Dr. Stockton said:

[Lots of good basic grounding for sorting tables -- but much snipped here]

I have an instinctive feeling that handling table elements may be slower
than handling elements of a corresponding array. If speed matters,
check that.

I feel that way too, but have no knowledge to back that feeling up

The built-in sort method is likely to be faster than a home-brew, if
given a well-considered sort function or if not needing one.

If you have to sore something unhelpful, such as US-format date strings
or dates containing letters, every comparison will need two of those to
be rendered comparable, and sorting tends to take N log N or more
comparisons. Therefore, in such cases, do a preliminary pass to
generate directly comparable sort keys.

No, the sortable data will include a Lot Number (e.g., 234, 613, or 1),
A name in the form 'Surname, Fname' and (in the future a street address in
the form '7204 E. Baywood Ave.' or 'nnnn C. Stname, CCC'

Assume that rows are to be stable, and sorted into the order of a
particular column. I think that if you represent the entire structure
as an array of rows, with the rows being arrays, with the zero element
of a row holding the sort key, and the rest of the array holding the
table data however convenient, then you can use the built-in sort after
setting the keys to suit the order desired.

Will mull on the above. In an earlier post I thought (when my CGI
app was building the phone directory, that I might easily place a hidden
array on the page to help the sorting algorithm -- whatever it is.

The art of sorting lies in not moving the actual data, just adjusting
what are in effect pointers. That's easy in JavaScript.

Be aware that there is no need to sort on demand. The page can be
fetched containing, for example, an "2-D" array of rows, and other
simple arrays indexing the data in all orders on offer. Then, when the
user "demands" a sort, just write the table in the desired order using
the appropriate one of those arrays.

If the user can input data, so that it cannot all be pre-sorted at
download, you can insert a pointer to the new data at the right position
of each list while the user is looking for the next data line.

No, the act of 'Editing' of my Phone Directory is a separate page (and
issue with all the check, balances needed. No rows will ever be added, only
the resident's data will change. Indeed, when the editing is complete and
confirmed, then the phone directory is rebuilt automatically by the CGI.

You can also sort all the downloaded data in JavaScript onload, with the
sort buttons temporarily disabled, distracting the user until the
buttons can be enabled,

<http://www.merlyn.demon.co.uk/js-order.htm> might help.

Thanks for the helpful guidance above. !

Denis, Lasse, and you are a real source of inspiration to me !

 

[Mel Smith]

I said:

The sort for each of the parameters took approx 20 seconds on my P5
machine. Maybe I should warn the user to 'sit back and relax' for a few
moments while the new table building is progressing )

Thanks again for this fast, perfect work (I'm jealous of your experience
and speed )

Denis (& others):


I did some timing tests on the full address book (613 lots ):

Results:

The 'sorting' took only 47 millisecs
The clearing of the table to 187 millisecs
The rebuilding of the new table took 22,781 millisecs.

So, I guess the 'rebuild' of the table is where it takes most of the
time.

Thanks again!

-Mel Smith

 

[Denis McMahon]

Thanks again for this fast, perfect work (I'm jealous of your experience and
speed )

Perfect it isn't, the detection of the last empty record in a a table
with an odd number of records (for example) is very crude.

Rgds

Denis McMahon

 

[Denis McMahon]

The 'sorting' took only 47 millisecs
The clearing of the table to 187 millisecs
The rebuilding of the new table took 22,781 millisecs.

Hmm

It might be possible, instead of clearing and rebuilding the table, to
just update the innerHTML of the cells.

I wonder how much quicker that would be .... there may be a second
variant of the code to try very shortly ...

In fact, there is now:

http://www.sined.co.uk/tmp/jstablesort2.htm

This version just over-writes the existing table cells with the new
data, rather than deleting and rebuilding the whole table, so I imagine
it will be a lot quicker.

Rgds

Denis McMahon