¿Qué es la ordenación por inserción en C?
El método de clasificación llamado clasificación por inserción hace coincidir cada elemento individual con los adyacentes a medida que itera a través de una matriz. Un elemento más pequeño que el anterior se inserta en el subarreglo ordenado en la ubicación adecuada.
Para ilustrar más, he demostrado un ejemplo en el que he considerado una matriz de cuatro elementos en una matriz como matriz[]= {5, 4, 60, 9} y queremos ordenar este elemento en orden ascendente usando la ordenación por inserción. Las siguientes interacciones explican el simulacro completo de la ordenación por inserción:
Iteración 1
| 5 | 4 | 60 | 9 |
Tenemos una matriz como arr[5, 4, 60, 9] ahora, en la primera iteración del ordenamiento por inserción, primero comparamos los dos primeros elementos, como 5 y 4, ya que arr[5] es > arr[4] entonces los intercambiamos para ordenar la matriz en orden ascendente. Ahora, la matriz será:
| 4 | 5 | 60 | 9 |
Iteración 2
| 4 | 5 | 60 | 9 |
En la segunda iteración, comparamos los siguientes dos elementos, como arr[5] con arr[60].
Como arr[5] < arr[60], el intercambio no ocurre porque ya está ordenado en orden ascendente. Ahora, la matriz se convierte en:
| 4 | 5 | 60 | 9 |
Iteración 3
| 4 | 5 | 60 | 9 |
Como en la tercera iteración, hacemos coincidir los elementos tercero y cuarto como arr[60] con arr[9].
Ahora, vemos que arr[60] > arr[9] por lo que se produce el intercambio, luego la matriz se ordenará en orden ascendente.
| 4 | 5 | 9 | 60 |
Así es como funciona la ordenación por inserción en C, que ordena un elemento de matriz fácilmente en orden ascendente o descendente.
Diagrama de flujo de clasificación por inserción
El siguiente es el diagrama de flujo del algoritmo de ordenación por inserción:
Ejemplo de implementación de ordenación por inserción en C
Primero requerimos una colección de elementos que deben ordenarse en orden ascendente y descendente para construir el método de ordenación por inserción en C. A los efectos de este ejemplo, supongamos que estamos tratando con una matriz de números. {5, 4, 60, 9} :
#incluirvacío inserciónordenar_ascendente ( En t arr1 [ ] , En t norte ) {
En t i , j , mi llave ;
//for loop se usa para iterar los valores i de 1 a i
para ( i = 1 ; i < norte ; i ++ ) {
mi llave = arr1 [ i ] ;
j = i - 1 ;
mientras ( j >= 0 && arr1 [ j ] > mi llave ) {
arr1 [ j + 1 ] = arr1 [ j ] ;
j = j - 1 ;
}
arr1 [ j + 1 ] = mi llave ;
}
}
vacío inserciónclasificación_descendente ( En t arr2 [ ] , En t metro ) {
En t i , j , mi llave ;
//se crea otro bucle for para iterar los valores i de 1 a i
para ( i = 1 ; i < metro ; i ++ ) {
mi llave = arr2 [ i ] ;
j = i - 1 ;
mientras ( j >= 0 && arr2 [ j ] < mi llave ) {
arr2 [ j + 1 ] = arr2 [ j ] ;
j = j - 1 ;
}
arr2 [ j + 1 ] = mi llave ;
}
}
En t principal ( ) {
//Inserción-Ordenar con orden descendente
En t mi_arr [ ] = { 5 , 4 , 60 , 9 } ; //inicializar un my_arr[] que tiene cuatro valores
En t metro = tamaño de ( mi_arr ) / tamaño de ( mi_arr [ 0 ] ) ;
inserciónclasificación_descendente ( mi_arr , metro ) ;
imprimir ( 'Array ordenado en orden descendente: ' ) ;
para ( En t i = 0 ; i < metro ; i ++ )
imprimir ( '%d ' , mi_arr [ i ] ) ;
imprimir ( ' \norte ' ) ;
//Inserción-Ordenar con orden ascendente
En t norte = tamaño de ( mi_arr ) / tamaño de ( mi_arr [ 0 ] ) ;
inserciónordenar_ascendente ( arr2 , norte ) ;
imprimir ( 'Array ordenado en orden ascendente:' ) ;
para ( En t i = 0 ; i < norte ; i ++ )
imprimir ( '%d ' , mi_arr [ i ] ) ;
imprimir ( ' \norte ' ) ;
devolver 0 ;
}
En este código, dos métodos inserciónordenar_descendente() , y inserciónordenar_ascendente() tomar los valores de la matriz de mi_arr[] . A continuación, el código utiliza un en bucle para iterar a través de los elementos de la matriz.
Llamamos a ambas funciones en la función principal una vez que hayan ordenado las matrices en orden descendente y ascendente. Después de eso, los bucles for se utilizan para imprimir la matriz ordenada.
Cuando ejecutamos este programa, el resultado esperado se coloca a continuación:
Conclusión
La ordenación por inserción es una forma rápida y sencilla de ordenar una matriz en secuencia ascendente o descendente. Para conjuntos de datos pequeños, esta técnica de clasificación funciona bien. Como puede ver en la guía anterior, es simple implementar un ejemplo de un programa en C para comprender fácilmente la ordenación por inserción en orden ascendente y descendente.