Shellsort gráfico (from Wikipedia)Hace unos días tuve que lidiar con un problema común en el diseño de aplicaciones web: ordenar bajo demanda las filas de una tabla según el valor de una columna concreta. Evidentemente lo primero que hice fue buscar por Internet alguna solución que me permitiera no tener que programar demasiado... y tengo que decir que lo encontré, pero por pequeños detalles nada de eso me sirvió.

Así que en este artículo explicaré el código que acabé picando yo por mi cuenta. Lo que he escrito depende de jQuery, aunque en realidad se puede sustituir por su "subconjunto" Sizzle, o incluso por la microbiblioteca Zepto.JS (que tiene una sintaxis compatible con la de jQuery).

Vayamos pues al código directamente, he creado un fichero llamado tablesorter.js en el que está todo el código necesario, salvo la llamada a una función, que se hace allí donde nos convenga :) .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

function row_comparer (row1, row2, index) {
	var r1 = $(row1).find('td').filter(function(){
                        return $(this).index() === index;
        }).text().toUpperCase();
	var r2 = $(row2).find('td').filter(function(){
                        return $(this).index() === index;
        }).text().toUpperCase();
 
	return  (r1 > r2)? 1:
	       ((r1 < r2)?-1:0);
}
 
function shsort (list, comparer, order) { // Shell sort (with Marcin Ciura's gaps)
	var gaps = [701, 301, 132, 57, 23, 10, 4, 1],
	    s = list.length,
	    t;
 
	for (var k=0; k<8; k++) { // 8 is gaps size
		for (var g = gaps[k], i=g; i<s; i++) {
			t = list[i];
			for (var j = i; j >= g && order*comparer(list[j-g], t) == 1; j-= g) {
				list[j] = list[j - g];
			}
			list[j] = t;
		}
	}
}
 
function sort_table (table, index, order) {
	var tbody = table.find ('tbody');
	var rows = tbody.find('tr');
 
	var comparer = function (row1, row2) {
		return row_comparer (row1, row2, index);
	}
 
	shsort (rows, comparer, order);
 
	tbody.html('');
	tbody.append (rows);
}
 
function setup_sortable (selector) {
	$(selector).each (function (i1) {
		$(this).find('th').each (function (i2) {
			var order = 1;
 
			$(this).click ( function () {
				sort_table ($(this).closest('table'), i2, order);
 
				order *= -1;
			})
		});
	});
}

Supongo que algunos de los que leéis esto preferiríais que hubiese creado un plugin para jQuery, siento decir que no es así. Eso no es por ninguna razón en particular, simplemente pasa que todavía no me he tomado la molestia de aprender como se hace, y no sé si es complicado o no, supongo que en breve habrá una versión en forma de plugin para jQuery :) .

En cuanto a como usarlo, la función setup_sortable debe ser llamada utilizando como parámetro un selector para las tablas a las que queramos aplicar ordenación "automática" (con este script las tablas se ordenan cuando se hace click en los elementos th de la tabla, básicamente las cabeceras). En mi caso añadí la clase sortable a todas las tablas que quería añadir esta característica y usé el selector ".sortable".

En cuanto al código, supongo que es destacable que hago un uso intensivo de las funciones anónimas y las clausuras, aunque no es nada que deba sorprender a nadie. En mi humilde opinión, lo más interesante es el algoritmo de ordenación, un "simple" Shell sort (basado en Insertion Sort).

Escogí este algoritmo por las siguientes razones:

  • Es estable, es decir, se mantiene el orden relativo entre elementos con la misma clave (el valor que se usa para realizar las comparaciones) que había en la lista antes de la ordenación. Esto es útil cuando queremos ordenar por distintos criterios a la vez.
  • Es de fácil implementación, solo tenéis que ver el código. Aquí puede parecer un poco más complicado porque uso la función comparer en vez del típico operador de comparación, pero no es una gran dificultad.
  • No usa recursión, ni pilas: los requisitos de memoria son pequeños y constantes.
  • Dependiendo de la implementación (y en particular con esta se consigue), se tiene que para ordenar una lista se deben realizar solo una cantidad de operaciones del orden de O(n·log²(n)).
  • Se trata de una rara avis, le cogí cariño. Aunque no se trata de un algoritmo destacable por su rendimiento, resulta que es tremendamente complicado a nivel teórico. Tanto que su velocidad depende fuertemente de una serie de parámetros de los que casi no se sabe nada a día de hoy. Yo he usado los de Marcin Ciura, que hasta donde yo sé, son los mejores encontrados hasta el momento.

Bien, hasta aquí el apunte de hoy :) . Espero que os pueda resultar útil, agradeceré cualquier comentario.. y si a alguien le interesa, estoy abierto a aceptar ayuda en la jqueryzación de esta minilibrería. Saludos!