Schweppes Sorting Algotihm - Conceptos básicos

Buenas a todos y todas!

Tras el pequeño parón, volvemos a la carga... y mientras termino de pulir BigInteger en versión CUDA (ya queda poco!), vamos a ver un pequeño algoritmo de ordenado que me vino a la mente, después de estudiar una curiosa paradoja.

¡Vamos allá!

Así, vamos a ver el SSA (Schweppes Sorting Algorithm), que es una evolución del clásico Bubble Sort (de ahí llamarlo Schweppes, ya que es mi refresco favorito :-) ).

Como podéis ver en el enlace, el Bubble Sort se basa en permutaciones únicas de elementos lineales (es decir, vamos pareja a pareja, consecutivamente, pivotando elementos).

Este algoritmo está inicialmente pensado para lenguajes de primera y segunda generación, es decir, no contamos con memoria dinámica - solamente estática.

Ahora bien, pasemos al principal concepto del algoritmo: la paradoja del grupo ordenado.

Para entender esta paradoja, hay que explicar el concepto de unión e intersección de grupos, lo que en informática tienen cantidad de nombres: "join", "joinkeys", "matching", "cruce", ... En definitiva, es la operación de suma, aplicada a conjuntos de datos.

Bien, supongamos que tenemos un conjunto de datos "A", que contiene los datos "{2, 4, 6}"; por otra parte, tenemos un conjunto de datos "B", que contiene los datos "{1, 4, 6}".

Si aplicamos la intersección entre "A" y "B", tendríamos como resultado:

A ∩ B = {4, 6}

En el campo de sistemas gestores de bases de datos, a esta operación se la conoce como "join". Bien, dentro del ámbito de los "join", o de las operaciones de conjuntos, disponemos de una gran variedad de operaciones... para nuestro caso, vamos a centrarnos en la operación conocida como "full outer join", que, en el mundo de los conjuntos, sería la unión entre "A" y "B"

A U B = {1, 2, 4, 4, 6, 6}

Ahora bien, ¿os habéis dado cuenta que he escrito el resultado de la unión como un conjunto ordenado? Bien podría haber escrito "{2, 4, 6, 1, 4, 6}", que sería primero los elementos de "A" y luego los elementos de "B"... pero resulta que, cuando hacemos un "full outer join", o un "full matching", o como lo queramos llamar en el mundo de la informática, trabajamos con conjuntos ordenados, y entregamos un conjunto ordenado.

Y ahí está la gracia, y la paradoja, del SSA. Usamos el concepto de conjuntos ordenados para generar un conjunto ordenado. Pero... ¿cómo ordenamos esos dos conjuntos ordenados iniciales? Pues, con conjuntos ordenados.

¿Qué?

Ahí está la paradoja. Partimos de conjuntos ordenados para crear conjuntos ordenados, pero para disponer de estos conjuntos ordenados previamente necesitamos ordenar los conjuntos.

Pero, ¿y si os dijera que no siempre es necesario? Está claro que no podemos basarnos en la suerte, en el azar, o cualquier divina providencia cuando codificamos software, entonces ¿qué nos hemos perdido?

El conjunto unitario: "A = {n}"

Un conjunto con solo un elemento, es en sí un conjunto ordenado.

Y esa es la clave de todo esto. Porque, si hacemos "full outer join" de dos conjuntos ordenados, su tamaño resultante es la suma del tamaño de ambos conjuntos, y así será como trabajaremos.

De momento, estos es todo.

Ya veréis, en la próxima entrada, como vamos aplicando todo esto... os dejo con la inquietud, para que vayáis pensando un poco en todo esto.

¡Nos vemos!