Ordenación por inserción: algoritmo con C, C++, Java, Python Ejemplos
sarah chen
¿Qué es la clasificación por inserción?
La clasificación por inserción es uno de los algoritmos de clasificación por comparación que se utilizan para ordenar elementos iterando un elemento a la vez y colocando el elemento en su posición correcta.
Cada elemento se inserta secuencialmente en una lista ya ordenada. El tamaño de la lista ya ordenada inicialmente es uno. El algoritmo de ordenación por inserción garantiza que los primeros k elementos se ordenen después de la k-ésima iteración.
Características del algoritmo de clasificación por inserción
El algoritmo de ordenación por inserción tiene las siguientes características importantes:
- Es una técnica de clasificación estable, por lo que no cambia el orden relativo de elementos iguales.
- Es eficaz para conjuntos de datos más pequeños pero no eficaz para listas más grandes.
- Insertion Sort es adaptativo, lo que reduce su número total de pasos si está parcialmente ordenado. Formación se proporciona como insumo para hacerlo eficiente.
¿Cómo se inserta? Opera¿Funciona?
En el algoritmo de ordenación por inserción, la operación de inserción se utiliza para ordenar elementos desordenados. Ayuda a insertar un nuevo elemento en una lista ya ordenada.
Pseudocódigo de la operación de inserción:
Considere una lista A de N elementos.
A[N-1] is the element to be inserted in the sorted sublist A[0..N-2]. For i = N-1 to 1: if A[i] < A[i-1], then swap A[i] and A[i-1] else Stop
En el ejemplo anterior, se insertará un nuevo elemento 6 en una lista ya ordenada.
Paso 1) En comparación con el elemento adyacente izquierdo de A[5], 9 > 6, intercambiamos la posición de 9 y 6. Ahora el elemento 6 se mueve a A[4].
Paso 2) Ahora, comparamos A[4] y A[3], y encontramos que A[3] > A[4], nuevamente intercambiamos la posición de 6 y 8.
Paso 3) Ahora compare A[3] y A[2], ya que A[2] > A[3] intercambian la posición de 7 y 6.
Paso 4) Comparamos A[1] y A[2], y como A[1] < A[2], es decir, el elemento adyacente izquierdo ya no es mayor. Ahora concluimos que 6 se insertó correctamente y detenemos el algoritmo aquí.
Cómo funciona la clasificación por inserción
La operación de inserción que se analizó anteriormente es la columna vertebral de la ordenación por inserción. El procedimiento de inserción se ejecuta en cada elemento y, al final, obtenemos la lista ordenada.
La figura de ejemplo anterior demuestra el funcionamiento de la ordenación por inserción en la estructura de datos. Inicialmente, solo hay un elemento en la sublista ordenada, es decir, 4. Después de insertar A[1], es decir, 3, el tamaño de la sublista ordenada aumenta a 2.
C++ Programa de clasificación por inserción
#include <iostream>
using namespace std;
int main(){
//unsorted list
int unsorted[] = {9,8,7,6,5,4,3,3,2,1};
//size of list
int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);
//printing unsorted list
cout << "\nUnsorted: ";
for(int i = 0 ; i < size_unsorted ; i++){
cout << unsorted[i] << " ";
}
int current_element,temp;
for(int i = 1; i < size_unsorted; i++){
current_element = unsorted[i];
for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
//swapping if current element is lesser
temp = unsorted[j+1];
unsorted[j+1] = unsorted[j];
unsorted[j] = temp;
}
}
//printing sorted list
cout << "\nSorted: ";
for(int i = 0 ; i < size_unsorted ; i++){
cout << unsorted[i] << " ";
}
return 0;
}
Salida:
Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
Código C para ordenación por inserción
#include <stdio.h>
int main() {
//unsorted list
int unsorted[] = {9,8,7,6,5,4,3,3,2,1};
//size of list
int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);
//printing unsorted list
printf("\nUnsorted: ");
for(int i = 0 ; i < size_unsorted ; i++){
printf("%d ", unsorted[i]);
}
int current_element, temp;
for(int i = 1; i < size_unsorted; i++){
current_element = unsorted[i];
for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
//swapping if current element is lesser
temp = unsorted[j+1];
unsorted[j+1] = unsorted[j];
unsorted[j] = temp;
}
}
//printing sorted list
printf("\nSorted: ");
for(int i = 0 ; i < size_unsorted ; i++){
printf("%d ", unsorted[i]);
}
return 0;
}
Salida:
Output: Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
Python Programa de clasificación por inserción
#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]
#size of list
size_unsorted = len(unsorted)
#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
print(unsorted[i], end=" ")
for i in range(1, size_unsorted):
current_element = unsorted[i]
j = i - 1
while j >= 0 and unsorted[j] > current_element:
#swapping if current element is lesser
unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
j -= 1
#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
print(unsorted[i], end=" ")
Salida:
Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
Propiedades del ordenamiento por inserción
Estas son las propiedades importantes de la ordenación por inserción:
- En línea: La ordenación por inserción puede ordenar elementos a medida que los recibe. Es decir, si ya hemos ordenado una lista de elementos y agregamos algunos elementos más a las listas, entonces no necesitamos ejecutar todo el procedimiento de clasificación nuevamente. En cambio, solo necesitamos iterar sobre los elementos recién agregados.
- En su lugar: La complejidad espacial del algoritmo de ordenación por inserción es constante y no requiere espacio adicional. Este algoritmo ordena los elementos en su lugar.
- Estable: En la ordenación por inserción, no intercambiamos los elementos si sus valores son iguales. Por ejemplo, dos elementos, xey, son iguales y x aparece antes de y en listas no ordenadas, luego, en la lista ordenada, x aparecerá antes de y. Esto hace que la clasificación por inserción sea estable.
- Adaptado: A algoritmo de clasificación Es adaptativo si lleva menos tiempo si los elementos de entrada o el subconjunto de elementos ya están ordenados. Como comentamos anteriormente, el mejor tiempo de ejecución para la ordenación por inserción es O(N), y el peor tiempo de ejecución es O(N^2). La clasificación por inserción es uno de los algoritmos de clasificación adaptativos.
Complejidad de la ordenación por inserción
Complejidad espacial
La ordenación por inserción no requiere espacio adicional para ordenar los elementos, la complejidad del espacio es constante, es decir, O(1).
Complejidad de tiempo
Como la ordenación por inserción itera cada elemento simultáneamente, requiere N-1 pases para ordenar N elementos. En cada pase, puede hacer cero intercambios si los elementos ya están ordenados, o intercambios si los elementos están dispuestos en orden descendente.
- Para el pase 1, los swaps mínimos requeridos son cero y los swaps máximos requeridos son 1.
- Para el pase 2, los swaps mínimos requeridos son cero y los swaps máximos requeridos son 2.
- Para el pase N, el swap mínimo requerido es cero y el swap máximo requerido es N.
- El intercambio mínimo es cero, por lo que la mejor complejidad temporal es O(N) para iterar N pases.
- Los intercambios máximos totales son (1+2+3+4+..+N) i. N(N+1)/2, la peor complejidad de tiempo es O(N^2).
Aquí está la importante complejidad temporal de la ordenación por inserción:
- Complejidad del peor caso: O (n2): ordenar una matriz en orden descendente cuando está en orden ascendente es el peor de los casos.
- Mejora la complejidad del caso: O(n): Mejores Caso La complejidad ocurre cuando la matriz ya está ordenada, el bucle externo se ejecuta n veces mientras que el bucle interno no se ejecuta en absoluto. Solo hay n comparaciones. Por lo tanto, en este caso, la complejidad es lineal.
- Complejidad media del caso: O (n2): Ocurre cuando los elementos de una matriz aparecen en orden desordenado, que no es ni ascendente ni descendente.
Resumen
- La clasificación por inserción es un método de algoritmo de clasificación que se basa en la comparación.
- Es una técnica de clasificación estable, por lo que no cambia el orden relativo de elementos iguales.
- En cada elemento, se utiliza la operación de inserción para insertar el elemento en la sublista ordenada.
- La clasificación por inserción es un algoritmo de clasificación in situ.
- La peor y promedio complejidad temporal de la ordenación por inserción es cuadrática, es decir, O(N^2).
- La clasificación por inserción no requiere ningún espacio auxiliar.
