Smoothsort es un algoritmo de ordenación por comparación desarrollado por Edsger W. Dijkstra en 1.981, es una variante del algoritmo del Montículo-Heapsort y proporciona una mejora de su rendimiento de O (n log n) a O(n) si la entrada tiene algún nivel de ordenación, en este caso se ejecutará en tiempo lineal.
| Rendimiento – Complejidad | |||
| Mejor caso Ω | Peor caso O | Media Θ | Espacio |
| (n log n) → (n) | (n log n) | (n log n) | O(1) |
La diferencia con heapsort radica en la estructura del montón (árbol binario donde el padre es mayor que sus dos hijos), cuando este se construye, el elemento mayor está en el lado izquierdo, pero realmente debería estar en el lado derecho. Para mover el elemento mayor a su ubicación debemos intercambiarlo con otro elemento y luego hacer una reordenación (burbuja) para reequilibrar el montón, esta operación toma un tiempo Ω (log n), contribuyendo al tiempo de ejecución general de Ω (n lg n).
La idea inicial de Dijkstra es bastante obvia, construyamos el montón haciendo que el elemento mayor esté a la derecha y nos ahorramos operaciones. Pero surge un problema, al quitar el mayor del montón romperemos el montón en otros dos con mayores distintos y debemos reequilibrarlos, para obtener un sólo nuevo mayor aplicamos una nueva reordenación (burbuja) que es decisiva en tiempo, llevará Ω (log n), lo que nos sitúa otra vez en un tiempo de ejecución Θ (n log n) y la idea de Dijkstra es obtener O (n) en el mejor de los casos. Vale, entonces en vez de tener un sólo montón mayor, tengamos una secuencia de montones mayores en el vector, de esta forma y siempre que no tengamos muchos de ellos, podremos encontrar eficientemente el elemento más grande de lo que queda.
Los montones divididos no son binarios, sino un tipo especial denominado números de Leonardo = {1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, …}. La utilización de estos números provoca que los elementos superiores (nodos) estén en orden ascendente y por tanto, el monton más a la derecha contiene el máximo de los elementos restantes.
Implementación en lenguaje Java.
//static int [] leo = {1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, ...
public static int[] ordenasmooth(int[] Vector) {
int tamañoV = Vector.length;
if (tamañoV == 0) return Vector;
int nodo = 0;
int posi = 0;
int divi = 0;
while (nodo < tamañoV) {
if ((divi & 3) == 3) {
divi >>>= 2;
posi = posi + 2;
} else if (posi > 1) {
divi <<= posi - 1;
posi = 1;
} else {
divi <<= posi;
posi = posi ^ 1;
}
divi++;
if ( posi > 0 && (tamañoV - nodo - 1) < (leo[posi - 1] + 1) ) {
smoothreorganizaV(Vector, nodo, divi, posi);
}
smoothcriba(Vector, nodo, posi);
nodo++;
}
smoothreorganizaV(Vector, nodo - 1, divi, posi);
while (nodo > 0) {
nodo--;
if (posi > 1) {
divi <<= 2;
divi--;
posi = posi - 2;
smoothreorganizaV(Vector, (nodo - leo[posi] - 1), divi >> 1, posi + 1);
smoothreorganizaV(Vector, nodo - 1, divi, posi);
} else {
int rastro = Integer.numberOfTrailingZeros(divi - 1);
divi >>= rastro;
posi = posi + rastro;
}
}
return Vector;
}
private static void smoothcriba(int[] Vector, int nodo, int posi) {
int nodotmp = Vector[nodo];
int ladoderecho = 0;
int ladoizquierdo = 0;
while (posi > 1) {
ladoderecho = nodo - 1;
ladoizquierdo = nodo - 1 - leo[posi - 2];
if (nodotmp >= Vector[ladoizquierdo] && nodotmp >= Vector[ladoderecho]) break;
if (Vector[ladoizquierdo] >= Vector[ladoderecho]) {
Vector[nodo] = Vector[ladoizquierdo];
nodo = ladoizquierdo;
posi = posi - 1;
} else {
Vector[nodo] = Vector[ladoderecho];
nodo = ladoderecho;
posi = posi - 2;
}
}
Vector[nodo] = nodotmp;
}
private static void smoothreorganizaV(int[] Vector, int nodo, int divi, int posi) {
int nodotmp = Vector[nodo];
while (divi > 1) {
int siguiente = nodo - leo[posi];
if (nodotmp >= Vector[siguiente]) break;
if (posi > 1) {
int ladoderecho = nodo - 1;
int ladoizquierdo = nodo - 1 - leo[posi - 2];
if (Vector[ladoizquierdo] >= Vector[siguiente] ||
Vector[ladoderecho] >= Vector[siguiente]) break;
}
Vector[nodo] = Vector[siguiente];
nodo = siguiente;
int rastro = Integer.numberOfTrailingZeros(divi - 1);
divi >>>= rastro;
posi = posi +rastro;
}
Vector[nodo] = nodotmp;
smoothcriba(Vector, nodo, posi);
}
Rendimiento.
Estadística individual realizada con el mismo equipo y condiciones del resumen de estadísticas de ordenación.
