La clasificación es una operación básica en la que los elementos de una matriz se organizan en algún orden específico para mejorar su capacidad de búsqueda. En palabras simples, los datos se ordenan para que puedan buscarse fácilmente.
Gráfica comparativa
| Bases para la comparación | Tipo de inserción | Selección de selección |
|---|---|---|
| BASIC | Los datos se ordenan insertando los datos en un archivo ordenado existente. | Los datos se ordenan seleccionando y colocando los elementos consecutivos en la ubicación ordenada. |
| Naturaleza | Estable | Inestable |
| Proceso a seguir | Los elementos se conocen de antemano mientras se busca la ubicación para colocarlos. | La ubicación es conocida previamente mientras se buscan elementos. |
| Datos inmediatos | La clasificación por inserción es una técnica de clasificación en vivo que puede tratar con datos inmediatos. | No puede tratar con datos inmediatos, necesita estar presente al principio. |
| La mejor complejidad del caso | En) | O (n 2 ) |
Definición de ordenación por inserción
La ordenación por inserción funciona al insertar el conjunto de valores en el archivo ordenado existente. Construye la matriz ordenada insertando un solo elemento a la vez. Este proceso continúa hasta que toda la matriz se ordena en algún orden. El concepto principal detrás de la ordenación por inserción es insertar cada elemento en su lugar apropiado en la lista final. El método de clasificación por inserción guarda una cantidad efectiva de memoria.
Trabajo del género Inserción.
- Utiliza dos conjuntos de matrices donde uno almacena los datos ordenados y otro en datos sin clasificar.
- El algoritmo de clasificación funciona hasta que haya elementos en el conjunto sin clasificar.
- Supongamos que hay 'n' elementos numéricos en la matriz. Inicialmente, el elemento con índice 0 (LB = 0) existe en el conjunto ordenado. Los elementos restantes están en la partición sin clasificar de la lista.
- El primer elemento de la parte sin clasificar tiene un índice de matriz 1 (Si LB = 0).
- Después de cada iteración, elige el primer elemento de la partición sin clasificar y la inserta en el lugar adecuado en el conjunto ordenado.
Ventajas de la ordenación por inserción.
- Se implementa fácilmente y es muy eficiente cuando se usa con pequeños conjuntos de datos.
- El requisito de espacio de memoria adicional de la ordenación por inserción es menor (es decir, O (1)).
- Se considera una técnica de clasificación en vivo, ya que la lista se puede clasificar a medida que se reciben los nuevos elementos.
- Es más rápido que otros algoritmos de clasificación.
Ejemplo:
Definición de selección de selección
La ordenación por selección realiza la clasificación buscando el número de valor mínimo y colocándolo en la primera o última posición según el orden (ascendente o descendente). El proceso de buscar la llave mínima y colocarla en la posición correcta continúa hasta que todos los elementos se colocan en la posición correcta.
Trabajo de selección por selección
- Supongamos una matriz ARR con N elementos en la memoria.
- En la primera pasada, se busca la clave más pequeña junto con su posición, luego ARR [POS] se intercambia con ARR [0]. Por lo tanto, ARR [0] está ordenado.
- En la segunda pasada, de nuevo, la posición del valor más pequeño se determina en el subarreglo de elementos N-1. Intercambie el ARR [POS] con ARR [1].
- En la pasada N-1, se realiza el mismo proceso para ordenar el número N de elementos.
Ejemplo:
Diferencias clave entre la ordenación por inserción y la ordenación por selección
- La ordenación por inserción usualmente realiza la operación de inserción. Por el contrario, la selección por selección lleva a cabo la selección y el posicionamiento de los elementos requeridos.
- Se dice que la ordenación por inserción es estable, mientras que la ordenación por selección no es un algoritmo estable.
- En el algoritmo de ordenación por inserción los elementos son conocidos previamente. En contraste, la ordenación de selección contiene la ubicación de antemano.
- La clasificación por inserción es una técnica de clasificación en vivo en la que los elementos que llegan se clasifican inmediatamente en la lista, mientras que la clasificación por selección no puede funcionar bien con datos inmediatos.
- La ordenación por inserción tiene el tiempo de ejecución O (n) en el mejor de los casos. A diferencia de, la mejor complejidad de tiempo de ejecución de orden de selección es O (n2).
Complejidad de ordenación por inserción
El mejor caso de complejidad de ordenación por inserción es O (n) veces, es decir, cuando la matriz está ordenada previamente. De la misma manera, cuando la matriz se ordena en orden inverso, el primer elemento de la matriz sin clasificar se comparará con cada elemento del conjunto ordenado. Entonces, en el peor de los casos, el tiempo de ejecución de la ordenación de inserción es cuadrático, es decir, O (n2) . En el caso promedio también tiene que hacer las comparaciones mínimas (k-1) / 2. Por lo tanto, el caso promedio también tiene un tiempo de ejecución cuadrático O (n2).
Complejidad de la selección por selección
Como el trabajo de selección, la clasificación no depende del orden original de los elementos en la matriz, por lo que no hay mucha diferencia entre el mejor y el peor caso de complejidad de la selección.
La ordenación de selección selecciona el elemento de valor mínimo, en el proceso de selección se escanea todo el 'n' número de elementos; por lo tanto, las comparaciones n-1 se hacen en la primera pasada. Entonces, los elementos se intercambian. Del mismo modo, en la segunda pasada también para encontrar el segundo elemento más pequeño, se requiere la exploración de los elementos n-1 y el proceso continúa hasta que toda la matriz se ordena.
Por lo tanto, la complejidad del tiempo de ejecución de la ordenación de selección es O (n2) .
= (n-1) + (n-2) + ……… .. + 2 + 1
= n (n-1) / 2 = O (n2)
Conclusión
Entre los dos algoritmos de clasificación, la clasificación por inserción es rápida, eficiente y estable, mientras que la clasificación por selección solo funciona de manera eficiente cuando está involucrado el pequeño conjunto de elementos o la lista está parcialmente ordenada previamente. El número de comparaciones realizadas por clasificación de selección es mayor que los movimientos realizados, mientras que en la clasificación por inserción, el número de veces que un elemento se mueve o se intercambia es mayor que las comparaciones realizadas.
