heapsort

El método de ordenación por residuos, o RadixSort, utiliza una aproximación diferente a la de comparar los elementos del arreglo entre sí. En vez de esto, este algoritmo recorre el arreglotrasladando cada elemento a una cola determinada por el residuo, o dígito menos significativo del número. Cuando todos los elementos han sido trasladados a las colas, se recorren todas las colas en ordentrasladando ahora los elementos al vector. El proceso se repite ahora para los demás dígitos de los elementos del vector.

Si bien se habla de digitos (unidades, decenas, centenas, etc), para uncomputador es más eficiente hacer las operaciones a nivel de bit, con desplazamientos, que las operaciones de división y residuo. Por tal motivo, la implementación que se presenta a continuación utilizacorrimientos de 4 bits, que se pueden representar como dígitos hexadecimales.


?
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
32public static void ordenacionResiduos(int[] v) {
int max = 1; // cantidad de repeticiones
int nbytes = 4; // numero de bytes a desplazar
int nColas = (int)Math.pow(2,nbytes) ;
// Creación e inicialización del arreglo de colas
Queue[] cola = new LinkedList[nColas];
for(int i=0; i>div) & 0xf;cola[numCola].add(numero);
}
div = div+nbytes;

// parte 2: recorrer las colas en orden para poner cada
// elemento en el vector;
int j=0;for(Queue c: cola) {
while(!c.isEmpty()) v[j++]=c.remove();
}
// la primera vez se actualiza el número de veces que se
// debe ejecutar el procesoif(i==0) { max = (int) (Math.log(max)/Math.log(nColas)) + 1; }
}
}


La complejidad de este algoritmo es lineal, O(NxM), donde N es el número de elementos del arreglo y M...