Hvad er Insertion Sort in C?
Sorteringsmetoden kaldet insertion sort matcher hvert enkelt element med tilstødende, når det itererer på tværs af en matrix. Et mindre element end det før det indsættes i det sorterede underarray på det passende sted.
For yderligere at illustrere har jeg demonstreret et eksempel, hvor jeg har overvejet en matrix af fire elementer i en matrix som f.eks. arr[]= {5, 4, 60, 9} og vi ønsker at sortere dette element i stigende rækkefølge ved at bruge insertion sort. Følgende interaktioner forklarer den komplette tørre kørsel af indsættelsessort:
Gentagelse 1
| 5 | 4 | 60 | 9 |
Vi har et array som arr[5, 4, 60, 9] nu, i den første iteration af indsættelsessortering sammenligner vi først de første to elementer såsom 5 og 4, da arr[5] er > arr[4] så vi bytter dem for at sortere arrayet i stigende rækkefølge. Nu vil arrayet være:
| 4 | 5 | 60 | 9 |
Gentagelse 2
| 4 | 5 | 60 | 9 |
I den anden iteration sammenligner vi de næste to elementer, såsom arr[5] med arr[60].
Da arr[5] < arr[60], så sker der ikke bytte, da det allerede er sorteret i stigende rækkefølge. Nu bliver arrayet:
| 4 | 5 | 60 | 9 |
Gentagelse 3
| 4 | 5 | 60 | 9 |
Som i den tredje iteration matcher vi det tredje og det fjerde element som arr[60] med arr[9].
Nu ser vi, at arr[60] > arr[9], så der sker ombytning, så vil arrayet sortere i stigende rækkefølge.
| 4 | 5 | 9 | 60 |
Sådan fungerer indsættelsessortering i C, som nemt sorterer et array-element i stigende eller faldende rækkefølge.
Flowdiagram over indsættelsessortering
Følgende er rutediagrammet for algoritmen for indsættelsessortering:
Implementeringseksempel på indsættelsessortering i C
Vi kræver først en samling af elementer, der skal sorteres i faldende og stigende rækkefølge for at bygge indsættelsessorteringsmetoden i C. Antag i forbindelse med dette eksempel, at vi har at gøre med en matrix af tal {5, 4, 60, 9} :
#includeugyldig insertionsort_ascending ( int arr1 [ ] , int n ) {
int jeg , j , min_nøgle ;
//for loop bruges til at iterere i-værdierne fra 1 til i
til ( jeg = 1 ; jeg < n ; jeg ++ ) {
min_nøgle = arr1 [ jeg ] ;
j = jeg - 1 ;
mens ( j >= 0 && arr1 [ j ] > min_nøgle ) {
arr1 [ j + 1 ] = arr1 [ j ] ;
j = j - 1 ;
}
arr1 [ j + 1 ] = min_nøgle ;
}
}
ugyldig insertionsort_descending ( int arr2 [ ] , int m ) {
int jeg , j , min_nøgle ;
//en anden for loop er oprettet for at iterere i-værdierne fra 1 til i
til ( jeg = 1 ; jeg < m ; jeg ++ ) {
min_nøgle = arr2 [ jeg ] ;
j = jeg - 1 ;
mens ( j >= 0 && arr2 [ j ] < min_nøgle ) {
arr2 [ j + 1 ] = arr2 [ j ] ;
j = j - 1 ;
}
arr2 [ j + 1 ] = min_nøgle ;
}
}
int vigtigste ( ) {
//Indsættelse-Sortér med faldende rækkefølge
int min_arr [ ] = { 5 , 4 , 60 , 9 } ; //initialiser en my_arr[] med fire værdier
int m = størrelse på ( min_arr ) / størrelse på ( min_arr [ 0 ] ) ;
insertionsort_descending ( min_arr , m ) ;
printf ( 'Sorteret matrix i faldende rækkefølge: ' ) ;
til ( int jeg = 0 ; jeg < m ; jeg ++ )
printf ( '%d' , min_arr [ jeg ] ) ;
printf ( ' \n ' ) ;
//Indsættelse-Sortér med stigende rækkefølge
int n = størrelse på ( min_arr ) / størrelse på ( min_arr [ 0 ] ) ;
insertionsort_ascending ( arr2 , n ) ;
printf ( 'Sorteret matrix i stigende rækkefølge: ' ) ;
til ( int jeg = 0 ; jeg < n ; jeg ++ )
printf ( '%d' , min_arr [ jeg ] ) ;
printf ( ' \n ' ) ;
Vend tilbage 0 ;
}
I denne kode, to metoder insertionsort_descending() , og insertionsort_ascending() tage matrixværdierne af min_arr[] . Koden bruger så en for sløjfe at iterere gennem arrayets elementer.
Vi kalder begge funktioner i hovedfunktionen, når de har sorteret arrays i faldende og stigende rækkefølge. Derefter bruges for-løkkerne til at udskrive det sorterede array.
Når vi kører dette program, er det forventede output placeret nedenfor:
Konklusion
Indsættelsessorteringen er en hurtig og nem måde at sortere et array i enten faldende eller stigende rækkefølge. For små datasæt fungerer denne sorteringsteknik godt. Som du kan se i vejledningen ovenfor, er det enkelt at implementere et eksempel på et C-program for nemt at forstå indsættelsessortering i faldende såvel som stigende rækkefølge.