Introducción a los algoritmos de clasificación de Java
La clasificación es el proceso de reorganizar un conjunto de elementos en un orden específico. La clasificación es esencial en el procesamiento de datos para que las aplicaciones puedan acceder a ellas de manera más eficiente. Se puede hacer un ejemplo de clasificación utilizando bases de datos con cláusulas en declaraciones SQL como “Orden por” o “Grupo por”.
El algoritmo es una secuencia de método/instrucciones que pueden ser seguido para pis, una tarea específica, como el cálculo y el procesamiento de datos.
Por lo tanto, un algoritmo de clasificación es un algoritmo con el propósito de reorganizar elementos en un orden específico. En el contexto de la informática o el procesamiento de datos, los elementos ordenados mediante la clasificación de los algoritmos son los datos, los archivos o las matrices.
No siempre es posible decir que un algoritmo es mejor que otro, ya que el rendimiento relativo puede Varíe dependiendo del tipo de datos que se están ordenando. En algunas situaciones, la mayoría de los datos están en el orden correcto, con solo unos pocos elementos que necesitan ser ordenados. En otras situaciones, los datos están completamente mezclados en un orden aleatorio y en otros los datos tenderán a estar en orden inverso. Diferentes algoritmos funcionarán de manera diferente según los datos que se están ordenando.
por ejemplo: cuando se usa una búsqueda avanzada de una consulta en particular, el motor de búsqueda usará un algoritmo de clasificación para clasificar sus resultados.
allí son muchos tipos de algoritmos de clasificación utilizados, a continuación se mencionan algunos ejemplos y comparaciones de los algoritmos de clasificación.
Categorías de clasificación
- Clasificación por intercambio – sort de burbujas, Quicksort
- Clasificación por inserción – Sorteo de inserción, shellsort
- Clasificación por selección – clasificación de selección, HeApsort
- clasificación fusionando – clasificación de fusiones
- Clasificación por distribución – Radix Sort
Complejidad de los algoritmos de clasificación
La complejidad de un algoritmo de clasificación mide el Tiempo de ejecución en función de n, el número de registros ordenados. Las siguientes son las operaciones fundamentales que tienen lugar durante la clasificación:
1.Comparison de dos claves
2. Intercambio de registros
3.Asignación de un registro A una ubicación temporal
Normalmente, la función de complejidad mide solo el número de comparaciones, ya que el número de otras operaciones es casi un factor constante del número de comparaciones.
Tipos de algoritmos de clasificación
Sorteo de burbujas
La clasificación de burbujas funciona comparando cada elemento de la lista con el elemento junto a él e intercambiándolos si es requerido. Con cada pase, el más grande de la lista está “burbujeante” hasta el final de la lista, mientras que los valores más pequeños se hunden en la parte inferior. Es similar al tipo de selección, aunque no es tan sencillo. En lugar de “seleccionar” valores máximos, se burbujean a una parte de la lista. Un único “paso de burbujas” completo es el paso en el que un elemento máximo está burbujeado a su posición correcta. Esto se maneja por el bucle interno para el bucle.
Examine la siguiente tabla. (tenga en cuenta que cada pase representa el estado de la matriz después de la finalización del bucle interno para el bucle, excepto para el pase 0, que representa la matriz a medida que se pasó a la función para clasificar)
8 6 10 3 1 2 5 4} Pase 0
6 8 3 1 2 5 4 10} Pase 1
6 3 1 2 5 4 8 10} Pase 2
3 1 2 5 4 6 8 10} Pase 3
1 2 3 4 5 6 8 10} Pase 4
1 2 3 4 5 6 8 10} Pase 5
1 2 3 4 5 6 8 10} Pase 6
1 2 3 4 5 6 8 10} Pase 7
El tabulado anterior representa claramente cómo funciona cada clasificación de burbujas. Tenga en cuenta que cada pase da como resultado que un número se burbujee hasta el final de la lista.
Ordena de selección
La idea de clasificación de selección es bastante simple. Básicamente determina el mínimo (o máximo) de la lista y la cambia con el elemento en el índice donde se supone que debe estar. El proceso se repite de tal manera que el enésimo elemento mínimo (o máximo) se cambie con el elemento en el índice N-1TH de la lista.
Considere la siguiente tabla. (tenga en cuenta que cada pase representa el estado de la matriz después de la finalización del bucle interno para el bucle, excepto para el pase 0, que representa la matriz a medida que se pasó a la función para clasificar)
8 6 10 3 1 2 5 4} Pase 0
1 6 10 3 8 2 5 4} Pase 1
1 2 10 3 8 6 5 4} Pase 2
1 2 3 10 8 6 5 4} Pase 3
1 2 3 4 8 6 5 10} Pase 4
1 2 3 4 5 6 8 10} Pase 5
1 2 3 4 5 6 8 10} Pase 6
1 2 3 4 5 6 8 10} Pase 7
En el pase 0, la lista no está ordenada. A continuación se encuentra el pase 1, en el que el elemento mínimo 1 se selecciona y se intercambia con el elemento 8, en el índice más bajo 0. En el paso 2, sin embargo, solo se considera el sublista, excluyendo el elemento 1. SO El elemento 2, se cambia con el elemento 6, en la segunda posición de índice más baja. Este proceso continúa hasta que la subconjunción se reduce a un solo elemento en el índice más alto (que es su posición correcta).
El algoritmo de clasificación de inserción es un algoritmo de uso común. Incluso si no ha sido un programador o un estudiante de informática, es posible que haya utilizado este algoritmo. Intenta recordar cómo ordenas un mazo de cartas. Comienza desde el principio, atraviesa las tarjetas y, a medida que encuentra tarjetas fuera de lugar, las eliminas e inserte en la posición correcta. Eventualmente lo que tienes es un mazo de cartas ordenado. La misma idea se aplica en el algoritmo de clasificación de inserción.
Examine la siguiente tabla. (tenga en cuenta que cada pase representa el estado de la matriz después de la finalización del bucle interno para el bucle, excepto para el pase 0, que representa la matriz a medida que se pasó a la función para clasificar)
8 6 10 3 1 2 5 4} Pase 0
6 8 10 3 1 2 5 4} Pase 1
6 8 10 3 1 2 5 4} Pase 2
3 6 8 10 1 2 5 4} Pase 3
1 3 6 8 10 2 5 4} Pase 4
1 2 3 6 8 10 5 4} Pase 5
1 2 3 5 6 8 10 4} Pase 6
1 2 3 4 5 6 8 10} Pase 7
El pase 0 es solo para mostrar el estado de la matriz no organizada antes de que se entregue al bucle para clasificar. Ahora pruebe el algoritmo de clasificación de la cubierta de tarjetas con esta lista y vea si coincide con los datos tabulados. Por ejemplo, comienza desde 8 y la siguiente tarjeta que ve es 6. Por lo tanto, elimina 6 de su posición actual e “inserte” de vuelta a la parte superior. Eso constituyó el Pase 1. Repita el mismo proceso y hará lo mismo para 3 que se inserta en la parte superior. Observe en el pase 5 que 2 se mueve de la posición 5 a la posición 1 desde su 1. A medida que continúa hasta que llega al final de la lista, encontrará que la lista ha sido ordenada .
sort de shell
Mejora con el orden de la burbujas y la clasificación de inserción al moverse fuera de orden más de una posición a la vez. Se puede describir que una implementación organiza la secuencia de datos en una matriz bidimensional y luego clasifica las columnas de la matriz utilizando el orden de inserción. Aunque este método es ineficiente para grandes conjuntos de datos, es uno de los algoritmos más rápidos para clasificar pequeños números de elementos (conjuntos con menos de 1000 elementos). Otra ventaja de este algoritmo es que requiere cantidades relativamente pequeñas de memoria.
Visualizar el tipo de shell de la siguiente manera: Organice la lista en una tabla y ordene las columnas (usando un tipo de inserción. Repita este proceso, Cada vez con un número menor de columnas más largas. Al final, la tabla tiene solo una columna. Mientras transformar la lista en una tabla hace que sea más fácil de visualizar, el algoritmo en sí hace su clasificación en el lugar (al incrementar el índice por el paso tamaño, es decir, usando i+= step_size en lugar de i ++).
Por ejemplo, considere una lista de números como [13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10]. Comenzó con un paso de 5 de 5, podríamos visualizar esto como romper la lista de números en una tabla con 5 columnas. Esto se vería así:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
Luego ordenamos cada columna, lo que nos da
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
Cuando leemos como una lista única de números, obtenemos [10 14 73 25 23 13 27 94 39 25 59 94 65 82 45]. Aquí, el 10 que fue al final, se ha movido hasta el principio. Esta lista se clasifica nuevamente utilizando un tipo de 3-GAP, y luego 1-GAP SUD (clasificación de inserción simple).
Merge Sort
Merge Sort aprovecha la facilidad de fusionar Listas ya ordenadas en una nueva lista ordenada. Comienza comparando cada dos elementos (es decir, 1 con 2, luego 3 con 4 …) y intercambiándolos si el primero debe venir después del segundo. Luego fusiona cada una de las listas resultantes de dos en listas de cuatro, luego fusiona esas listas de cuatro, y así sucesivamente; Hasta que al final se fusionan dos listas en la lista final ordenada.
Merge Sort incorpora dos ideas principales para mejorar su tiempo de ejecución:
Una pequeña lista tomará menos pasos para clasificar que una gran lista. Se requieren menos pasos para construir una lista ordenada a partir de dos listas ordenadas que dos listas no organizadas. Por ejemplo, solo tiene que atravesar cada lista una vez si ya están ordenadas (consulte la función de fusión a continuación para una implementación de ejemplo).
Ventajas y desventajas
Clasificación de burbujas
ventajas
- Bastante fácil de entender en términos de clasificación de algoritmos
- Bastante fácil de escribir (es decir, aproximadamente 5 líneas de código)
Desventajas
- Algoritmo relativamente lento
- es decir, o (n^2) para completar la clasificación
Normación de inserción
ventajas
- tiene en cuenta los elementos de la lista que ya están ordenados
- Por lo tanto, funcionan bastante bien para una lista parcialmente ordenada
< Desventajas
- Todavía un algoritmo relativamente lento
- Especialmente si la lista de inicio está en orden inverso
clasificación de selección
ventajas
- fácil de entender
- Por lo tanto, fácil de implementar
Desventajas
- No se puede reconocer partes de la lista parcialmente ordenada
- Funciona solo en las partes no organizadas
- El método usa clasificación interna (es decir. Requiere que la matriz completa esté en la memoria, a veces grandes cantidades de memoria)
Criterios a la clasificación de los algoritmos de clasificación
- La complejidad computacional de los tamaños de elementos , según el tamaño del elemento en la lista (N), puede ser peor, promedio o mejor. Las buenas comparaciones son o (n log n) mientras que las malas son o (n2))
- Complejidad computacional de los swaps , según los algoritmos “en su lugar”
- El uso y el uso de la memoria de otros recursos de la computadora – Ejemplo: una gran clase de algoritmo es la clasificación “en el lugar” que es más lenta que el algoritmo que utiliza memoria adicional
- Establidad – El algoritmo de clasificación estable mantiene órdenes relativas de registros con claves iguales, ya que todas las claves diferentes considerarán esta distinción inútil
- recursión – recursivo, no recursivo o ambas </li
- La naturaleza de clasificación de comparación – tiene o no tiene
- Métodos generales – intercambio (es decir, clasificación de burbujas), selección (es decir, Heapsort), fusionando, etc …
- comportamientos en conjuntos de datos importantes – si está completamente ordenado, inversamente ordenado y casi ordenado
Código de muestra
La siguiente función utilizada en c ++:
en línea int swap (int & x;, int & y;) {
int z = x;
x = y;
y = z;
}
Referencias
Animación de clasificación, http://www.google.com.sg/search?hl=en&q; = Define%3a+algoritmo & btng; = google+search & meta; =
Introducción al algoritmo de clasificación, http://webspace.ship.edu/cawell/sorting/main.htm
Algorithms de clasificación , http://homepages.north.londonmet.ac.uk/~chalkp/proj/algtutor/sortingal.html
Comparación de algoritmo de clasificación, http://www.cprogramming.com/tutorial/Computersciencetheory/ sortcomp.html
stable sa, http://planetmath.org/encyclopedia/stablesortingalgorithm.html
http://www.cogx.com/cogx/ctw/algorithms/defleult .html
http://linux.wku.edu/~lamonml/algor/sort/sort.html
http://www.ics.uci.edu/~epstein /161/960116.html
http://atschool.eduweb.co.uk/mbaker/sorts.htm
http://sig9.com/articles/sorting-algorithms
