ALGORITMO COUNTING SORT

IMPLEMENTACION EN JAVA DEL ALGORITMO DE ORDENAMIENTO COUNTING SORT

El Counting Sort es uno de los algoritmos básicos de ordenamiento. En este articulo traigo una propuesta de código en Java.

¿Como funciona el algoritmo CountingSort?

El ordenamiento por cuentas (counting sort en inglés) es un algoritmo de ordenamiento en el que se cuenta el número de elementos de cada clase para luego ordenarlos. Sólo puede ser utilizado por tanto para ordenar elementos que sean contables (como los números enteros en un determinado intervalo, pero no los números reales, por ejemplo).

El primer paso consiste en averiguar cuál es el intervalo dentro del que están los datos a ordenar (valores mínimo y máximo). Después se crea un vector de números enteros con tantos elementos como valores haya en el intervalo [mínimo, máximo], y a cada elemento se le da el valor 0 (0 apariciones). Tras esto se recorren todos los elementos a ordenar y se cuenta el número de apariciones de cada elemento (usando el vector que hemos creado). Por último, basta con recorrer este vector para tener todos los elementos ordenados.

Código en java del algoritmo CountingSort

Hoy les traigo una implementacion en Java del algoritmo de ordenamiento Counting Sort. Este algoritmo tiene superioridad a otros algoritmos de ordenamiento o al clásico algoritmo en el que hacemos dos ciclos y un arreglo auxiliar, pues este algoritmo tiene un tiempo de ejecución muy favorable.

Para que no te salte ningún error, debes crear una clase llamada Algoritmos.

Recomendado:   APP INVENTOR: CREAR APP CON BOTONES DE REDES SOCIALES
public class Algoritmos {

/*
* Algoritmo2
*/
public int[] countinsort(int[] A) {
int n = A.length-1;
int k = A[0];
for (int i = 1; i <= n; i++) {
if (A[i] > k) {
k = A[i];
}
}
int[] C = new int[k + 1];

for (int i = 0; i <= k; i++) {
C[i] = 0;
}
for (int i = 0; i <= n; i++) {
C[A[i]] = C[A[i]] + 1;
}
for (int i = 1; i <= k; i++) {
C[i] = C[i] + C[i - 1];
}
int[] B = new int[n+1];
for (int i = n ; i >= 0; i--) {
C[A[i]] = C[A[i]] - 1;
B[C[A[i]]] = A[i];
}
return B;
}

public void imprimir (int []a){
String res="";
for (int i = 0; i < a.length; i++) {
res=res+a[i]+", ";
}
System.out.println(res);
}

public static void main(String[] args) {
Algoritmos a = new Algoritmos();
int arre []= {10,9,8,7,150,6,5,4,3,2,1};
a.imprimir(a.countinsort(arre));
}

}

Espero que este algoritmo Counting Sort en Java sea de tu agrado. Si tienes alguna propuesta, puedes dejarla en los comentarios. No olvides calificar este articulo.

Entradas relacionadas