Foro Analisis
Foro Analisis
Foro Analisis
Foro Semana 5 y 6
Integrantes:
Carlos Augusto Sabino Cañizares
Características:
Se trata de un algoritmo estable cuya complejidad computacional es O(n+k),
siendo n el número de elementos a ordenar y kel tamaño del vector auxiliar
(máximo - mínimo).
La eficiencia del algoritmo es independiente de lo casi ordenado que estuviera
anteriormente. Es decir no existe un mejor y peor caso, todos los casos se tratan
iguales.
El algoritmo counting, no se ordena in situ, sino que requiere de una memoria
adicional.
Limitaciones:
Sólo puede ser utilizado en determinadas circunstancias.
Sólo ordena números enteros, no vale para ordenar cadenas y es desaconsejable
para ordenar números decimales.
Otra limitación (por ineficiencia) incluso con números enteros es cuando el rango
entre el mayor y el menor es muy grande.
El pseudocódigo sería el siguiente:
Ordenamiento_por_Cuenta( A, B, k )
1 for i <-- 1 to k
2 do C[i] <-- 0
3 for j <-- 1 to tamaño[A]
4 do C[ A[j] ] <-- C[ A[j] ] + 1
5 // C[i] contiene ahora el número de elementos igual a 'i'
6 for i <-- 2 to k
7 do C[i] <-- C[i] + C[i-1]
8 // C[i] contiene ahora el número de elementos menor que o igual a 'i'
9 for j <-- tamaño[A] downto 1
10 do B[ C[ A[j] ] ] <-- A[j]
11 C[ A[j] ] <-- C[ A[j] ] - 1
Veamos:
Símbolo Significado
^
Paso 1 Paso 2
1 2 3 4 5 1 2 3 4
3 4 4 3 3 0 0 3 2
Paso 3 Paso 4
1 2 3 4 1 2 3 4 5
0 0 2 5 3
Paso 5 Paso 6
1 2 3 4 1 2 3 4 5
0 0 2 5 3 3
1 2 3 4 1 2 3 4 5
0 0 1 5 3 3 4
Paso 9 Paso 10
1 2 3 4 1 2 3 4 5
0 0 1 4 3 3 4 4
11. Paso 11
12. Pasos 9-10, con j=1
Paso 11 Paso 12
1 2 3 4 1 2 3 4 5
0 0 1 3 3 3 3 4 4
Paso 13
1 2 3 4
0 0 0 3
14. j = 0, por lo tanto se sale del bucle for. B da lugar al resultado, que es el
ordenamiento de A:
Paso 14
1 2 3 4 5
3 3 3 4 4
Después que los datos de entrada han pasado por los diferentes ciclos de
este algoritmo. Finalizara cuando todos los valores de entrada estén en su
posición correspondiente.
import java.util.*;
/*
Sort the array right to the left
1) Look up in the array of occurences the last occurence of the given
value
2) Place it into the sorted array
3) Decrement the index of the last occurence of the given value
4) Continue with the previous value of the input array (goto set1),
terminate if all values were already sorted
*/
for (int i = array.length - 1; i >= 0; i--) {
aux[counts[array[i] - min]--] = array[i];
}
return aux;
}
}
}
Radixt sort
Radix Sort es uno de los algoritmos de clasificación lineal más eficientes y
rápidos. Es fácil de entender y fácil de implementar. Radix Sort es una buena
opción para muchos programas que necesitan una clasificación rápida.
Radix Sort puede manejar claves más grandes de manera más eficiente en
comparación con Counting Sort.
Radix-Sort(A, d)
//It works same as counting sort for d number of passes.
//Each key in A[1..n] is a d-digit integer.
//(Digits are numbered 1 to d from right to left.)
for j = 1 to d do
//A[]-- Initial Array to Sort
int count[10] = {0};
//Store the count of "keys" in count[]
//key- it is number at digit place j
for i = 0 to n do
count[key of(A[i]) in pass j]++
for k = 1 to 10 do
count[k] = count[k] + count[k-1]
end for(j)
end func
En la clasificación de radix, primero ordenamos los elementos según el último
dígito (el dígito menos significativo). Luego, el resultado se clasifica
nuevamente por segundo dígito, continúe este proceso para todos los dígitos
hasta que alcancemos el dígito más significativo. Usamos el orden de conteo
para ordenar los elementos de cada dígito, por lo que la complejidad del
tiempo es O (nd), donde ), donde n es el tamaño de la matriz y d es el número
de dígitos en el número más grande.
class Radix {
// A utility function to get maximum value in arr[]
static int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
Bucket sort
función bucket-sort(elementos, n)
casilleros ← colección de n listas
para i = 1 hasta longitud(elementos) hacer
c ← buscar el casillero adecuado
insertar elementos[i] en casillero[c]
fin para
para i = 1 hasta n hacer
ordenar(casilleros[i])
fin para
devolver la concatenación de casilleros[1],..., casilleros[n]
Se procede a llenar los "buckets" con los elementos que pertenezcan al intervalo:
En el primer paso se tienen que encontrar los valores máximo y mínimo del arreglo
para poder determinar cuales serán los intervalos que trabajará cada "bucket", una
vez determinados se tienen que extraer los elementos del arreglo y pasar cada
uno a su "bucket" correspondiente.
---
Bucket Sort se origina a partir del método Counting Sort. Counting Sort lo que
hace es solo separar cada número del arreglo original, y después se coloca de
vuelta en su lugar final. Bucket Sort básicamente está haciendo lo mismo, excepto
que lo hace con múltiples números a la vez.
package bucket.sort;
import java.util.*;
public class BucketSort {
private static int i;
public static Vector<Integer> sort(Vector<Integer> lista, int inferior,int superior)
{
int rango= (superior-inferior);
int bucket_size = rango/10;
/*
agregamos cada uno de los elemento en la lista que corresponde
*/
for(int i=0;i<lista.size();i++)
{
/* calculamos en la lista que le corresponde */
int casilla = (lista.elementAt(i)-inferior)/bucket_size;
/* Agregamos el elemento a la lista calculada */
Vector<Integer> vCasilla = listas.elementAt(casilla);
vCasilla.addElement(lista.elementAt(i));
}
for(int i=0;i<10000;lista.addElement(r.nextInt(10000)),i++);
System.out.println("Imprimiendo generados");
for(int i=0;i<lista.size();System.out.println(lista.elementAt(i++)));
System.out.println("");
Fin=System.currentTimeMillis();
Tiempo=Fin-Inicio;
System.out.println("Tiempo Que Tarda En Ejecutar 10,000 Numeros");
System.out.println(+Tiempo+" Mili Segundos");
}
}
Cuadro comparativo ( Counting Sort, Bucket sort, radix sort, string
sort)
Eficiencia:
No existe un mejor y peor caso, todos los casos se
tratan iguales
Facilidad de implementación:
Utiliza el diapasón de los números del array a
ordenar (lista) para calcular los elementos que
coinciden.
Restricciones:
Sólo puede ser aplicado en elementos en un
intervalo de a lo más k elementos, típicamente en
números naturales en el rango de 1 a k. Su cota
de tiempo es de O (n + k), por lo que para ser mejor
que el ordenamiento a base de comparaciones, se
debe cumplir que k < O.
Eficiencia:
Es eficiente y veloz método de ordenamiento
interno.
Facilida de implementación:
Se trata de una generalización del algoritmo
Pigeonhole sort. Cuando los elementos a ordenar
están uniformemente distribuidos la complejidad
computacional de este algoritmo es de O(n).
Restricciones:
Requiere más memoria auxiliar para los cubos a
costa del tiempo de ejecución que más géneros de
comparación. Funciona en O (n + k)
O (n + k) tiempo en el caso promedio donde n es la
cantidad de elementos que se ordenarán y k es la
cantidad de cubos.
Eficiencia:
Es rápido a diferencia de otros algoritmos de
ordenamiento.
Facilidad de implementación:
Hacer una clasificación dígito por dígito
comenzando desde el dígito menos significativo
hasta el dígito más significativo.
Restricciones:
No podemos usar la ordenación por conteo porque
la clasificación por conteo tomará O (n 2 ).
Aunque:
Para seleccionar exactamente uno, debemos identificar básicamente
el escenario adecuado para saber de esta manera con que algoritmo
se debe operar con el fin de optimizar el mejor caso y encontrar una
solución rápida,
Porque, algunos algoritmos lentos se comportan en un orden
cuadrático, es decir, O(n²), mientras que los algoritmos rápidos se
comportan, en un caso promedio en un orden logarítmico, es decir, O
(n log n). Con esta base podremos tener la idea de que algoritmo será
el apropiado.
Además:
Al utilizar informaci´on adicional de los elementos es posible diseñar
algoritmos de ordenamiento que corren en tiempo o(n log n)
• Counting-Sort asume que los elementos a ordenar son n enteros
en el rango {0, . . . , k} y corre en tiempo Θ(n + k)
• Radix-Sort asume que los elementos a ordenar son n enteros de a
lo sumo d d´ıgitos y corre en tiempo Θ(dn)
• Bucket-Sort asume que los elementos a ordenar son n n´umeros
reales en [0, 1) generados de forma uniforme e independiente, y
corre en tiempo esperado Θ(n)
Bibliografía
Counting Sort, Bucket sort, radix sort, string sort. (s.f.). Algoritmos de Ordenamiento (
Counting Sort, Bucket sort, radix sort, string sort). Recuperado el 17 de junio de
2019, de https://www.u-cursos.cl/ingenieria/2010/2/CC4102/1/blog/o/2035
Artículos con clase. (s.f.). Ordenamiento por Cuenta (Counting Sort). Recuperado el 21 de
junio de 2019, de
http://articulos.conclase.net/?tema=ordenacion&art=cuenta&pag=000
CODINGEEK. (s.f.). Clasificación de radix - explicación, pseudocódigo e implementación.
Recuperado el 21 de junio de 2019, de
https://www.codingeek.com/algorithms/radix-sort-explanation-pseudocode-and-
implementation/
GeerForGeeks. (s.f.). Radix Sort. Recuperado el 19 de junio de 2019, de
https://www.geeksforgeeks.org/radix-sort/
javacodex.com. (s.f.). Counting Sort. Recuperado el 22 de junio de 2019, de
https://www.javacodex.com/Sorting/Counting-Sort
Neocities Ordenamientos. (s.f.). Neocities Ordenamientos Sort. Recuperado el 17 de junio
de 2019, de https://bucketsort.neocities.org/ejemplo.html
Wikipedia. (s.f.). Ordenamiento por casilleros. Recuperado el 17 de junio de 2019, de
https://es.wikipedia.org/wiki/Ordenamiento_por_casilleros
Wikipedia. (s.f.). Ordenamiento por cuentas. Recuperado el 21 de junio de 2019, de
https://es.wikipedia.org/wiki/Ordenamiento_por_cuentas#Limitaciones