Metodo radix sort

RadixSort

- Vemos claramente que RadixSort es estable porque la función que procesa todo es “CountingSort” y la estabilidad de esta la analizamos en la pagina anterior. Además el FOR de RadixSort no influye en la estabilidad.
- También notamos que no se basa en la comparación para ordenar ya que CountingSort tampoco lo hace, solo con los FORs ordena pero sin comparar entre los valores de las claves. El FOR de RadixSort no hace comparaciones.
- Claramente este algoritmo utiliza memoria adicional, ya que se basa en la ejecución de CountingSort que ocupa un arreglo temporal que deber cargado en memoria para poder copiar los valores ordenadamente al output.
- Como habíamos demostrado antes el tiempo de ejecución de CountingSort es de O(n) entonces ahora CountingSort se ejecuta “d” veces con un d lista[j+1])
4. temp = lista[j];
5. lista[j] = lista[j+1];
6. lista[j+1] = temp;
1. for (i=0; i temp) && (j >= 0) )
5. lista[j+1] = lista[j];
6. j--;
7. lista[j+1] = temp;