En este tutorial, aprenderá cómo funciona la ordenación por inserción. Además, encontrará ejemplos prácticos de ordenación por inserción en C, C ++, Java y Python.
La clasificación por inserción funciona de manera similar a como clasificamos las cartas en nuestra mano en un juego de cartas.
Suponemos que la primera tarjeta ya está ordenada, luego seleccionamos una tarjeta sin clasificar. Si la carta sin clasificar es mayor que la carta en la mano, se coloca a la derecha de lo contrario, a la izquierda. De la misma manera, se toman otras cartas sin clasificar y se colocan en su lugar correcto.
El ordenamiento por inserción utiliza un enfoque similar.
La ordenación por inserción es un algoritmo de ordenación que coloca un elemento sin clasificar en su lugar adecuado en cada iteración.
¿Cómo funciona el ordenamiento por inserción?
Supongamos que necesitamos ordenar la siguiente matriz.
Matriz inicial
- Se supone que el primer elemento de la matriz está ordenado. Tome el segundo elemento y guárdelo por separado
key.
Comparekeycon el primer elemento. Si el primer elemento es mayor quekey, la clave se coloca delante del primer elemento.
Si el primer elemento es mayor que clave, entonces la clave se coloca delante del primer elemento. - Ahora, los dos primeros elementos están ordenados.
Toma el tercer elemento y compáralo con los elementos de la izquierda. Lo colocó justo detrás del elemento más pequeño que él. Si no hay ningún elemento más pequeño que él, colóquelo al principio de la matriz.
Coloque 1 al principio - De manera similar, coloque cada elemento sin clasificar en su posición correcta.
Coloque 4 detrás de 1 
Coloque 3 detrás de 1 y la matriz se ordena
Algoritmo de ordenación por inserción
insertionSort (matriz) marca el primer elemento como ordenado para cada elemento no ordenado X 'extrae' el elemento X para j X mueve el elemento ordenado hacia la derecha en 1 bucle de ruptura e inserta X aquí end insertionSort
Ejemplos de Python, Java y C / C ++
Python Java C C ++ # Insertion sort in Python def insertionSort(array): for step in range(1, len(array)): key = array(step) j = step - 1 # Compare key with each element on the left of it until an element smaller than it is found # For descending order, change keyarray(j). while j>= 0 and key < array(j): array(j + 1) = array(j) j = j - 1 # Place key at after the element just smaller than it. array(j + 1) = key data = (9, 5, 1, 4, 3) insertionSort(data) print('Sorted Array in Ascending Order:') print(data)
// Insertion sort in Java import java.util.Arrays; class InsertionSort ( void insertionSort(int array()) ( int size = array.length; for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (j>= 0 && key < array(j)) ( array(j + 1) = array(j); --j; ) // Place key at after the element just smaller than it. array(j + 1) = key; ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 5, 1, 4, 3 ); InsertionSort is = new InsertionSort(); is.insertionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Insertion sort in C #include // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( printf("%d ", array(i)); ) printf(""); ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); printf("Sorted array in ascending order:"); printArray(data, size); )
// Insertion sort in C++ #include using namespace std; // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); cout << "Sorted array in ascending order:"; printArray(data, size); )
Complejidad
Complejidades de tiempo
- Complejidad del peor de los casos: supongamos que una matriz está en orden ascendente y desea ordenarla en orden descendente. En este caso, ocurre la complejidad del peor de los casos. Cada elemento debe compararse con cada uno de los otros elementos, por lo que, para cada enésimo elemento, se realiza un número de comparaciones. Por tanto, el número total de comparaciones =
O(n2)(n-1)n*(n-1) ~ n2 - Mejor complejidad de caso:
O(n)
cuando la matriz ya está ordenada, el bucle externo se ejecutanvarias veces, mientras que el bucle interno no se ejecuta en absoluto. Entonces, solo hay unnnúmero de comparaciones. Por tanto, la complejidad es lineal. - Complejidad de casos promedio: ocurre cuando los elementos de una matriz están en orden desordenado (ni ascendente ni descendente).
O(n2)
Complejidad espacial
La complejidad del espacio se O(1)debe a que keyse utiliza una variable adicional .
Aplicaciones de clasificación por inserción
La ordenación por inserción se utiliza cuando:
- la matriz tiene una pequeña cantidad de elementos
- solo quedan algunos elementos por ordenar
