Algoritmos de clasificación en Java - Diferentes tipos de algoritmos de clasificación en Java

• Introducción a los algoritmos de clasificación en Java

Introducción a los algoritmos de clasificación en Java

Ordenar la información en un cierto orden, a menudo dentro de un marco tipo matriz, es organizarlos. Puede usar diferentes requisitos de secuencia, los más populares son la clasificación de números de menor a mayor o viceversa, o la clasificación lexicográfica de cadenas. Cubriremos diferentes algoritmos, desde alternativas ineficaces pero intuitivas hasta algoritmos eficientes implementados efectivamente en Java y en otros lenguajes si está interesado en cómo funciona la ordenación.

Diferentes algoritmos de ordenación en java

Existen diferentes algoritmos de clasificación y no todos son igualmente efectivos. Para compararlos y ver cuáles funcionan mejor, analizaremos sus complejidades temporales.

1. Tipo de inserción
2. Ordenamiento de burbuja
3. Selección Ordenar
4. Ordenar fusión
5. Heapsort

1. Ordenar por inserción

El concepto detrás de Insertion Sort divide el rango en las submatrices que están ordenadas y sin clasificar. La porción clasificada está al comienzo de la duración 1 y coincide con el primer componente (lado izquierdo) en la matriz. Nos movemos a través de la matriz y expandimos la parte clasificada de la matriz en un componente durante cada iteración. Cuando nos expandimos, colocamos el elemento nuevo en la submatriz ordenada. Hacemos esto moviendo todos los elementos hacia la derecha hasta que descubramos que no tenemos que cambiar el primer componente. Cuando la porción en negrita se ordena en orden ascendente, por ejemplo, en la siguiente matriz, ocurre:

1. 3 5 7 8 4 2 1 9 6: Considere 4 e inserte esto es lo que necesitamos. Hemos estado cambiando desde 8> 4
2. 2. 3 5 7 x 8 2 1 9 6
3. 3 5 x 7 8 2 1 9 6
4. 3 x 5 7 8 2 1 9 6
5. 3 4 5 7 8 2 1 9 6

Código:

public class InsertionSortEx (
public static void insertionSort(int() arr) (
for (int x = 1; x < arr.length; x++) (
int current = arr(x);
int y = x - 1;
while(y >= 0 && current < arr(y)) (
arr(y+1) = arr(y);
y--;
)
arr(y+1) = current;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 7, 8, 4, 2, 1, 9, 6);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
insertionSort(arr1);//sorting array using insertion sort
System.out.println("After Insertion Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)

Salida:

Siguiendo este método, un componente extendió la parte ordenada, ahora tenemos cinco en lugar de cuatro elementos. Cada iteración hace esto y toda la matriz se ordenará al final.

Nota: Esto se debe a que necesitamos transferir la lista clasificada completa una por una en cada iteración, que es O (n). Para cada componente en cada tabla, debemos hacer esto, lo que implica que está O (n 2) limitado.2.

2. Ordenar burbujas

Si la burbuja no está en el orden requerido, opera reemplazando los componentes vecinos. Esto se repite hasta que todos los componentes estén en orden desde el inicio de la matriz. Sabemos que si logramos hacer la iteración completa sin intercambios, todos los elementos en comparación con sus elementos adyacentes estaban en el orden deseable y, por extensión, toda la matriz. La razón del algoritmo de clasificación de burbujas es que los números como "burbujean" en el "suelo". Si, después de una cantidad específica, vuelve a pasar por la instancia (4 es una buena instancia), notará que el número lentamente se mueve hacia la derecha

Los pasos para ordenar burbujas son los siguientes:

1. 4 2 1 5 3: Aquí, los dos ^primeros números no están en el orden correcto, por lo tanto, tenemos que ordenar ambos números.
2. 2 4 1 5 3: después de eso, el siguiente par de números tampoco está en el orden correcto. Entonces la clasificación ocurre nuevamente.
3. 2 1 4 5 3: Estos dos están en el orden correcto, 4 <5, por lo tanto, no es necesario intercambiarlos.
4. 2 1 4 5 3 : Nuevamente, tenemos que cambiar por el orden correcto.
5. 2 1 4 3 5: Aquí está la matriz resultante después de una iteración.
6. Tenemos que repetir este proceso nuevamente hasta que los números estén en el orden correcto.

Código:

public class BubbleSortExample (
public static void bubbleSort(int() arr) (
int n = arr.length;
int tmp = 0;
for(int x=0; x < n; x++)(
for(int y=1; y < (nx); y++)(
if(arr(y-1) > arr(y))(
//swap elements
tmp = arr(y-1);
arr(y-1) = arr(y);
arr(y) = tmp;
)
)
)
)
public static void main(String() args) (
int arr() =(4, 2, 1, 5, 3);
System.out.println("Array Before Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
System.out.println();
bubbleSort(arr);
System.out.println("Array After Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
)
)

Salida:

Nota: Podría haber terminado en un bucle infinito si usara a (i)> = a (i + 1), porque esa conexión aún sería válida con componentes equivalentes y, por lo tanto, siempre los cambiaría de un elemento a otro.

3. Selección de selección

Selección Ordenar divide la matriz en una matriz de clasificaciones que no están ordenadas. Esta vez, sin embargo, el subconjunto de clasificación se forma insertando al final del conjunto ordenado el elemento mínimo del subconjunto sin clasificar, intercambiando:

1. 3 5 1 2 4
2. 1 5 3 2 4
3. 1 2 3 5 4
4. 1 2 3 5 4
5. 1 2 3 4 5
6. 1 2 3 4 5

Código:

public class SelectionSortEx (
public static void selectionSort(int() arr)(
for (int x = 0; x < arr.length - 1; x++)
(
int indx = x;
for (int y = x + 1; y < arr.length; y++)(
if (arr(y) < arr(indx))(
indx = y;
)
)
int smallNumber = arr(indx);
arr(indx) = arr(x);
arr(x) = smallNumber;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 1, 2, 4);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
selectionSort(arr1);
System.out.println("After Selection Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)

Salida:

Nota: El mínimo es O (n) para el tamaño de la matriz porque se deben verificar todos los componentes. Para cada elemento de la matriz, debemos encontrar el mínimo y limitar todo el proceso O (n 2).

4. Combinar Ordenar

Merge Sort utiliza la recursividad para solucionar el problema del método de división y conquista de manera más efectiva que los algoritmos descritos anteriormente.

Este árbol muestra cómo funcionan las llamadas recursivas. Las matrices marcadas con flecha hacia abajo son matrices para las que llamamos función mientras fusionamos matrices de flecha hacia arriba. Luego sigues la flecha hasta el borde del árbol y luego regresas y te unes. Tenemos 3 5 3 1 rango, por lo que lo dividimos en 3 5 4 y 2 1. Los dividimos en sus partes para ordenarlos. Comenzamos a fusionarlos y clasificarlos a medida que avanzamos cuando llegamos al fondo.

Código:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class MergeSort (
static void merge(int() array, int lowval, int midval, int highval)(
int x, y, k;
int() c= new int(highval-lowval+1);
k = 0;
x=lowval;
y=midval+1;
while(x<=midval && y<=highval)(
if(array(x)<=array(y))(
c(k++) = array(x++);
)
else(
c(k++) = array(y++);
)
)
while(x<=midval)(
c(k++) = array(x++);
)
while(y<=highval)(
c(k++) = array(y++);
)
k=0;
for(x = lowval; x<=highval; x++)(
array(x) = c(k++);
)
)
static void mergeSort(int() array, int lowval, int highval)(
if(highval-lowval+1>1)(
int midval = (lowval+highval)/2;
mergeSort(array, lowval, midval);
mergeSort(array, midval+1, highval);
merge(array, lowval, midval, highval);
)
)
public static void main(String() args) (
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
int size;
System.out.println("Enter the array");
try (
size = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("Please Enter valid Input");
return;
)
int() array = new int(size);
System.out.println("Enter array elements");
int x;
for (x = 0; x < array.length; x++) (
try (
array(x) = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("An error Occurred");
)
)
System.out.println("After Sorting");
System.out.println(Arrays.toString(array));
mergeSort(array, 0, array.length-1);
System.out.println("Before Merge Sorting");
System.out.println(Arrays.toString(array));
)
)

En este programa, le hemos pedido al usuario que ingrese la entrada. La salida estará ordenada según la entrada del usuario.

Salida:

5. Heap Sort

Primero debe conocer el marco en el que opera Heapsort, el montón, para comprender por qué funciona. Hablaremos específicamente sobre un montón binario, pero también puede generalizar esto a otras construcciones de montón. Un montón es un árbol que cumple la propiedad del montón, es decir, que todos sus elementos secundarios tienen relaciones con cada nodo. Un montón también debe estar casi terminado. Un binario de profundidad d casi completo tiene un subárbol d-1, con la misma raíz, y cada nodo tiene un subárbol completo, izquierdo, con un descendente izquierdo.

En otras palabras, obtienes un número cada vez más bajo (montón mínimo) o más grande y más grande (montón máximo) cuando te mueves hacia abajo del árbol. Aquí hay una instancia de max-heap:

1. 6 1 8 3 5 2 4 : Aquí, los números de ambos niños son más pequeños que los padres, por lo tanto, no tenemos que cambiar nada.
2. 6 1 8 3 5 2 4: Aquí, 5> 1, necesitamos intercambiarlos. Necesitamos heapify para 5.
3. 6 5 8 3 1 2 4: los números de ambos niños son más pequeños, todo sigue igual.
4. 6 5 8 3 1 2 4: Aquí, 8> 6, por lo tanto, debemos intercambiarlos.
5. 8 5 6 3 1 2 4: Después de esta iteración, obtendremos este resultado.

Después de repetir este proceso nuevamente, obtendremos los siguientes resultados:

• 8 5 6 3 1 2 4

1. 4 5 6 3 1 2 8 : Intercambio
2. 6 5 4 3 1 2 8 : Heapify
3. 2 5 4 3 1 6 8 : Intercambio
4. 5 2 4 2 1 6 8 : Heapify
5. 1 2 4 2 5 6 8 : Intercambio

Código:

public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
) public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
)

Salida:

Puede verlo desde el punto hasta el nivel del gráfico, de izquierda a derecha. Lo que logramos aquí es que cuando tenemos el componente kth en la matriz, la posición de sus hijos es 2 \ * k + 1 y 2 \ * k + 2 (suponiendo que la indexación comienza en 0). Esto puede ser monitoreado por usted. La posición del padre es siempre (k-1) / 2 para el componente kth. Puedes fácilmente "apilar" cualquier rango, porque lo sabes. Compruebe si uno de sus elementos secundarios es más bajo que el de cada componente. Si es así, empareje un padre y repita este paso recursivamente con el padre.

Nota: Dado que iterar for-loops en toda la matriz hace heapSort) (obviamente O (N), crearía la complejidad general de Heapsort O (nlog n). Heapsort tiene un tipo en el lugar, lo que significa que requiere O (N 1) más espacio que Merge Sort, pero tiene algunas desventajas, como los paralelos que son difíciles.

Conclusión - Algoritmos de clasificación en Java

La clasificación es un procedimiento muy frecuente con conjuntos de datos, ya sea para un análisis posterior, acelerar la búsqueda con algoritmos más efectivos que se basan en información clasificada, filtrar información, etc. La clasificación está respaldada por varios idiomas y, a menudo, las interfaces oscurecen lo que hace el programador.

Artículos recomendados

Esta es una guía para ordenar algoritmos en Java. Aquí discutimos diferentes tipos de ordenación en Java junto con sus algoritmos. También puede consultar nuestros otros artículos sugeridos:

1. Fusionar algoritmos de clasificación en Java
2. JComboBox en Java
3. StringBuffer en Java
4. JTextField en Java
5. Heap Sort en Python
6. Algoritmos de clasificación rápida en Java
7. Guía completa para ordenar en C # con ejemplos
8. Algoritmos de clasificación en JavaScript
9. Guía de ejemplos de algoritmo de C ++
10. Guía completa para ordenar algoritmos en Python