Algoritmo de clasificación más rápido Java
Este artículo cubrirá los dos algoritmos de clasificación más rápidos y escribirá su código en Java.
La primera técnica es la clasificación por conteo, que tiene algunas limitaciones. Por lo tanto, también cubriremos el algoritmo Merge Sort.
Algoritmo de clasificación de conteo en Java
El algoritmo de clasificación por conteo es una de las técnicas de clasificación más rápidas que podemos usar cuando los elementos de la matriz se dan dentro de un rango específico. No es una técnica de clasificación basada en la comparación, pero clasifica la matriz contando y almacenando la frecuencia de cada elemento de la matriz.
En términos simples, utiliza hashing para ordenar la matriz.
Los usuarios deben seguir el siguiente algoritmo para el tipo de conteo.
-
Encuentre los elementos máximo y mínimo de la matriz.
-
A continuación, encuentre el rango de la matriz usando elementos máximos y mínimos y cree una nueva matriz de “frecuencia” de rango de tamaño para almacenar la frecuencia de cada elemento.
-
Iterar a través de la matriz original y almacenar la frecuencia de cada elemento en la matriz
freq. -
Al sumar las frecuencias, cuente las frecuencias acumuladas de cada elemento.
-
Comience a iterar a la matriz original desde el final y coloque cada elemento en su posición ordenada utilizando la matriz
freq. -
Almacene todos los elementos ordenados desde
resultadoen la matriz original para ordenar la matriz original.
Código de ejemplo:
class CountingSort {
// function to find the maximum from the array
static int findMax(int arr[]) {
int maxi = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maxi)
maxi = arr[i];
}
return maxi; // return maximum
}
// function to find the minimum from the array
static int findMin(int arr[]) {
int mini = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < mini)
mini = arr[i];
}
return mini; // return minimum
}
static void cntSort(int[] arr) {
int maxi = findMax(arr);
int mini = findMin(arr);
// getting range from maximum and minimum elements of the array
int range = maxi - mini + 1;
// creating the array to store the frequency of elements
int freq[] = new int[range];
// resultant array
int result[] = new int[arr.length];
// counting frequency of elements and storing it to freq array
for (int i = 0; i < arr.length; i++) {
freq[arr[i] - mini]++;
}
// Doing addition of frequency
for (int i = 1; i < freq.length; i++) {
freq[i] += freq[i - 1];
}
// Putting every element of arr to its correct place based on the freq array
for (int i = arr.length - 1; i >= 0; i--) {
result[freq[arr[i] - mini] - 1] = arr[i];
freq[arr[i] - mini]--;
}
// Make arr array sorted by assigning elements from the result array
for (int i = 0; i < arr.length; i++) {
arr[i] = result[i];
}
}
public static void main(String[] args) {
int[] arr = {10, 20, -2, -4, 3, 40, 50, 30, 20, 10};
cntSort(arr);
System.out.println("Sorted Array using counting sort is ");
for (int a = 0; a < arr.length; a++) {
System.out.print(arr[a] + " ");
}
}
}
Producción :
Sorted Array is -4 -2 3 10 10 20 20 30 40 50
Complejidad temporal del algoritmo de clasificación de conteo en Java
La complejidad de tiempo para Counting Sort es de orden lineal ya que estamos usando un solo bucle for.
| Mejor caso | O(n+k) |
| Caso promedio | O(n+k) |
| Peor de los casos | O(n+k) |
Complejidad espacial del algoritmo de clasificación de conteo en Java
La complejidad del espacio para la ordenación de conteo es O(n) ya que usamos la matriz temporal para almacenar elementos ordenados.
Limitaciones del algoritmo de clasificación de conteo en Java
La técnica de clasificación por conteo es el algoritmo más rápido para clasificar elementos de la matriz sin duda, pero tiene algunas limitaciones.
Los usuarios pueden pensar en el escenario donde la longitud de la matriz es muy pequeña y el rango de entrada es demasiado grande, como millones. Incluso Bubble Sort puede funcionar mejor en tales casos.
Por lo tanto, los usuarios pueden usarlo para ordenar la matriz en tiempo lineal cuando el rango de entrada es pequeño.
Combinar algoritmo de clasificación en Java
Para superar las limitaciones de Counting Sort, los usuarios pueden utilizar la técnica Merge Sort.
El algoritmo Merge Sort sigue el enfoque divide y vencerás. Primero, divide la matriz en dos mitades, la ordena y fusiona la matriz ordenada.
Para aprender el algoritmo completo paso a paso, los usuarios pueden seguir los pasos a continuación.
-
Encuentre el punto medio de la matriz.
-
Llame recursivamente a la función
mergeSort()para la primera y segunda parte de la matriz. -
Llame a la función
merge()para fusionar la matriz. -
En la función
merge(), cree dos arreglos temporales del mismo tamaño que dos partes del arreglo y almacene el elemento del arreglo en el arreglo temporal correspondiente. -
Repita los arreglos temporales hasta que ambos tengan elementos sin clasificar, encuentre el elemento mínimo de ambos arreglos, guárdelo en el arreglo original y siga moviéndose.
-
Si queda algún elemento en el
LeftArray, guárdelo en el array original y haga lo mismo con elRightArray.
Código de ejemplo:
class Test {
// function to merge two sorted arrays
static void merge(int arr[], int left, int mid, int right) {
// sizes for temp arrays
int n1 = mid - left + 1;
int n2 = right - mid;
// temp arrays
int LeftArray[] = new int[n1];
int RigthArray[] = new int[n2];
// clone data to temp arrays
for (int i = 0; i < n1; ++i) LeftArray[i] = arr[left + i];
for (int j = 0; j < n2; ++j) RigthArray[j] = arr[mid + 1 + j];
int a = 0, b = 0;
// merging temp arrays to the original array
int k = left;
while (a < n1 && b < n2) {
if (LeftArray[a] <= RigthArray[b]) {
arr[k] = LeftArray[a];
a++;
} else {
arr[k] = RigthArray[b];
b++;
}
k++;
}
// If any elements are left in LeftArray, clone it to the original array
while (a < n1) {
arr[k] = LeftArray[a];
a++;
k++;
}
// If any elements are left in RightArray, clone it to the original array
while (b < n2) {
arr[k] = RigthArray[b];
b++;
k++;
}
}
static void mergeSort(int arr[], int left, int right) {
if (left < right) {
// Find the mid of the array using the left and right
int mid = left + (right - left) / 2;
// sort the first half of the array
mergeSort(arr, left, mid);
// sort the second half of the array
mergeSort(arr, mid + 1, right);
// sort both parts of the array and merge it
merge(arr, left, mid, right);
}
}
public static void main(String args[]) {
int[] arr = {10, 201, -22121, -412, 3, 212121, 50, 30, 20, 1021212};
mergeSort(arr, 0, arr.length - 1);
System.out.println("Sorted array using merge sort is");
for (int a = 0; a < arr.length; a++) {
System.out.print(arr[a] + " ");
}
}
}
Producción :
Sorted array is -22121 -412 3 10 20 30 50 201 212121 1021212
Complejidad temporal del algoritmo Merge Sort en Java
La complejidad de tiempo para mergeSort() es O(nlogn), donde n es la longitud de la matriz. Aquí, la complejidad de tiempo de la función merge() es de O(n), y la complejidad de tiempo de la función mergeSort() es O(logn) ya que estamos haciendo una llamada recursiva para cada la mitad de la matriz.
| Mejor caso | O(nlog(n)) |
| Caso promedio | O(nlog(n)) |
| Peor de los casos | O(nlog(n)) |
Complejidad espacial del algoritmo Merge Sort en Java
La complejidad del espacio para la ordenación por fusión es de O(n) ya que usamos las dos matrices temporales para almacenar elementos no ordenados.
En este artículo, hemos aprendido paso a paso el algoritmo de clasificación por conteo, uno de los algoritmos más rápidos en Java, con su código de ejemplo. Además, para superar las limitaciones de la ordenación por conteo, hemos aprendido la ordenación por fusión, que funcionará para cualquier rango de entrada.
