# JavaScript: DHTML Bubble Sort

This page demonstrates the most simple sorting algorithm - the Bubble Sort. Using DHTML the table below can be sorted by any column in any direction.

## Working Demonstration

You can use the controls under the table to change the sort order and to add more rows containing random values.

id | colour | random |
---|---|---|

1 | blue | 598 |

2 | red | 625 |

3 | yellow | 815 |

4 | blue | 995 |

5 | blue | 228 |

6 | blue | 504 |

7 | yellow | 670 |

8 | green | 420 |

9 | yellow | 624 |

10 | green | 243 |

11 | purple | 800 |

12 | purple | 175 |

13 | yellow | 850 |

14 | yellow | 562 |

15 | yellow | 192 |

16 | yellow | 244 |

17 | green | 754 |

18 | yellow | 19 |

19 | orange | 617 |

20 | orange | 902 |

## How does it work?

The basic components of any sorting algorithm are the ability to:
`get` a value; `compare` values; and `exchange`
items. We have a function for each, but first we need some some global
variables:

If this doesn't sound like good programming practice to you then you probably want to look at the OOP version where it's wrapped in an object.

```
// global variables
var parent = null; // 'parent' node
var items = new Array(); // array of 'child' nodes
var col = 0; // column for sorting
```

While it's clear that the `items` in this case are going to be
the rows (TR's), it's not so clear what their parent node is. While you
might assume that TR's are children to the TABLE, it turns out that -
whether you code it or not - there's actually a TBODY node, a childNode
to TABLE, that contains the TR's.

```
<TABLE>
<THEAD>
(header row appears here - optional)
</THEAD>
<TBODY>
(data rows to be sorted appear here)
</TBODY>
</TABLE>
```

To make sure we have the right `parent` node, we check that it's
nodeName is `TBODY`, and if not, search for a `TBODY`
element within it. If you have some data in the table that needs to stay
on top, just insert a `THEAD` element around that row or rows.

The arguments to the sorting function are then:

**tableid**- an`id`identifying a`TABLE`or`TBODY`element;**n**- identifies which column of the`TABLE`we want to sort by; and**desc**- a boolean value indicating the direction of the sort.

```
function sortTable(tableid, n, desc)
{
// parent node identified by id="tableid"
parent = document.getElementById(tableid);
col = n;
// parent node for sorting rows must be TBODY and not TABLE
if(parent.nodeName != "TBODY")
parent = parent.getElementsByTagName("TBODY")[0];
if(parent.nodeName != "TBODY")
return false;
// assert: parent is now a TBODY node
items = parent.getElementsByTagName("TR");
var N = items.length;
// bubble sort - not very efficient but ok for short lists
for(var j=N-1; j > 0; j--) {
for(var i=0; i < j; i++) {
if(compare(get(i+1), get(i), desc)) exchange(i+1, i);
}
}
return true;
}
```

We don't need to go into the mechanics of the Bubble Sort itself. Suffice to say that it's a mechanical sorting process that's very reliable, but not very efficient.

## get, compare and exchange

The `get` function is relatively straight-forward. It selects
the i*th* row and then the col*th* table cell. The value for
sorting purposes is the value of the first `childNode` of the TD.

If the value found is numeric then it is returned as a number (an integer to be specific but you could probably handle floats in a similar way).

If the value within the `TD` is contained in
another tag (such as an `A` or `FONT` tag) then the function
will need to be modified. You can see one solution for this, as well as other enhancements, implemented
in the OOP version.

```
function get(i)
{
var node = items[i].getElementsByTagName("TD")[col];
if(node.childNodes.length == 0) return "";
// assumes firstChild of node is a textNode
var retval = node.firstChild.nodeValue;
if(parseInt(retval) == retval) return parseInt(retval);
return retval;
}
```

Nothing much to explain for the `compare` function:

```
function compare(val1, val2, desc)
{
return (desc) ? val1 > val2 : val1 < val2;
}
```

The `exchange` function is nice and compact. We insert one
element of the `items` array before it's predecessor. This
automatically removes it from it's previous position (to avoid
duplication) resulting in an exchange of adjacent rows.

```
function exchange(i, j)
{
// exchange adjacent items
parent.insertBefore(items[i], items[j]);
}
```

That's all there is to it. For more advanced (and complicated) sorting techniques, see the Insertion Sort, Shell Sort and Quick Sort demonstrations. Each one is (in theory) more efficient that the preceding algorithms.

## Related Articles - Sorting Algorithms

- JavaScript DHTML Sorting Algorithms
- JavaScript DHTML Quick Sort
- JavaScript DHTML Insertion Sort
- JavaScript
**DHTML Bubble Sort** - JavaScript Sorting Algorithm Comparison
- JavaScript DHTML Sorting Using OOP - Example 1
- JavaScript DHTML Shell Sort
- PHP Sorting Arrays of Arrays
- PHP Sorting SimpleXMLElement Object arrays