Ce este Insertion Sort în C?
Metoda de sortare numită sortare prin inserție potrivește fiecare element cu elemente adiacente pe măsură ce iterează printr-o matrice. Un element mai mic decât cel de dinainte de a fi introdus în subbary sortat în locația corespunzătoare.
Pentru a ilustra în continuare, am demonstrat un exemplu în care am luat în considerare o matrice de patru elemente într-o matrice, cum ar fi arr[]= {5, 4, 60, 9} și dorim să sortăm acest element în ordine crescătoare folosind sortarea prin inserție. Următoarele interacțiuni explică ciclul complet uscat al sortării prin inserție:
Iterația 1
| 5 | 4 | 60 | 9 |
Avem o matrice ca arr[5, 4, 60, 9] acum, în prima iterație a sortării prin inserție, comparăm mai întâi primele două elemente, cum ar fi 5 și 4, deoarece arr[5] este > arr[4] deci le schimbăm pentru a sorta matricea în ordine crescătoare. Acum, matricea va fi:
| 4 | 5 | 60 | 9 |
Iterația 2
| 4 | 5 | 60 | 9 |
În a doua iterație, comparăm următoarele două elemente, precum arr[5] cu arr[60].
Deoarece arr[5] < arr[60], schimbarea nu are loc deoarece este deja sortată în ordine crescătoare. Acum, matricea devine:
| 4 | 5 | 60 | 9 |
Iterația 3
| 4 | 5 | 60 | 9 |
Ca și în a treia iterație, potrivim al treilea și al patrulea element ca arr[60] cu arr[9].
Acum, vedem că arr[60] > arr[9] are loc schimbarea, apoi matricea va sorta în ordine crescătoare.
| 4 | 5 | 9 | 60 |
Acesta este modul în care funcționează sortarea prin inserție în C, care sortează cu ușurință un element de matrice în ordine crescătoare sau descrescătoare.
Diagramă de sortare a inserției
Următoarea este diagrama de flux a algoritmului de sortare a inserției:
Exemplu de implementare a sortării inserției în C
Mai întâi avem nevoie de o colecție de elemente care trebuie sortate în ordine descrescătoare și crescătoare pentru a construi metoda de sortare prin inserare în C. Să presupunem, în scopurile acestui exemplu, că avem de-a face cu o serie de numere. {5, 4, 60, 9} :
#includegol insertionsort_ascending ( int arr1 [ ] , int n ) {
int i , j , cheia mea ;
// bucla for este folosită pentru a repeta valorile i de la 1 la i
pentru ( i = 1 ; i < n ; i ++ ) {
cheia mea = arr1 [ i ] ;
j = i - 1 ;
in timp ce ( j >= 0 && arr1 [ j ] > cheia mea ) {
arr1 [ j + 1 ] = arr1 [ j ] ;
j = j - 1 ;
}
arr1 [ j + 1 ] = cheia mea ;
}
}
gol insertionsort_descending ( int arr2 [ ] , int m ) {
int i , j , cheia mea ;
//O altă buclă for este creată pentru a repeta valorile i de la 1 la i
pentru ( i = 1 ; i < m ; i ++ ) {
cheia mea = arr2 [ i ] ;
j = i - 1 ;
in timp ce ( j >= 0 && arr2 [ j ] < cheia mea ) {
arr2 [ j + 1 ] = arr2 [ j ] ;
j = j - 1 ;
}
arr2 [ j + 1 ] = cheia mea ;
}
}
int principal ( ) {
//Inserție-Sortează cu ordine descrescătoare
int my_arr [ ] = { 5 , 4 , 60 , 9 } ; //inițializați un my_arr[] având patru valori
int m = dimensiunea ( my_arr ) / dimensiunea ( my_arr [ 0 ] ) ;
insertionsort_descending ( my_arr , m ) ;
printf ( 'Matrice sortată în ordine descrescătoare: ' ) ;
pentru ( int i = 0 ; i < m ; i ++ )
printf ( „%d” , my_arr [ i ] ) ;
printf ( ' \n ' ) ;
//Inserție-Sortează în ordine crescătoare
int n = dimensiunea ( my_arr ) / dimensiunea ( my_arr [ 0 ] ) ;
insertionsort_ascending ( arr2 , n ) ;
printf ( 'Matrice sortată în ordine crescătoare: ' ) ;
pentru ( int i = 0 ; i < n ; i ++ )
printf ( „%d” , my_arr [ i ] ) ;
printf ( ' \n ' ) ;
întoarcere 0 ;
}
În acest cod, două metode insertionsort_descending() , și insertionsort_ascending() ia valorile matricei ale my_arr[] . Codul folosește apoi a pentru buclă pentru a itera prin elementele matricei.
Apelăm ambele funcții în funcția principală odată ce au sortat tablourile în ordine descrescătoare și crescătoare. După aceea, buclele for sunt folosite pentru a tipări matricea sortată.
Când rulăm acest program, rezultatul așteptat este plasat mai jos:
Concluzie
Sortarea prin inserare este o modalitate rapidă și ușoară de a sorta o matrice fie în secvență descendentă, fie ascendentă. Pentru seturile de date mici, această tehnică de sortare funcționează bine. După cum puteți vedea în ghidul de mai sus, este simplu să implementați un exemplu de program C pentru a înțelege cu ușurință sortarea inserției în ordine descrescătoare și crescătoare.