Kaj je razvrščanje z vstavljanjem v C?
Metoda razvrščanja, imenovana razvrščanje z vstavljanjem, ujema vsak posamezen element s sosednjimi, ko se ponavlja po matriki. Manjši element od tistega, preden je vstavljen v razvrščeno podmatriko na ustrezno lokacijo.
Za nadaljnjo ponazoritev sem prikazal primer, v katerem sem obravnaval niz štirih elementov v nizu, kot je npr. arr[]= {5, 4, 60, 9} in ta element želimo razvrstiti v naraščajočem vrstnem redu z uporabo razvrščanja z vstavljanjem. Naslednje interakcije pojasnjujejo popolno suho vožnjo razvrščanja vstavljanja:
Ponovitev 1
| 5 | 4 | 60 | 9 |
Zdaj imamo matriko kot arr[5, 4, 60, 9], v prvi ponovitvi razvrščanja z vstavljanjem najprej primerjamo prva dva elementa, kot sta 5 in 4, ker je arr[5] > arr[4], torej jih zamenjamo, da razvrstimo niz v naraščajočem vrstnem redu. Sedaj bo niz:
| 4 | 5 | 60 | 9 |
Ponovitev 2
| 4 | 5 | 60 | 9 |
V drugi ponovitvi primerjamo naslednja dva elementa, kot je arr[5] z arr[60].
Ker je arr[5] < arr[60], se zamenjava ne zgodi, ker je že razvrščen v naraščajočem vrstnem redu. Zdaj postane niz:
| 4 | 5 | 60 | 9 |
Ponovitev 3
| 4 | 5 | 60 | 9 |
Tako kot v tretji ponovitvi ujememo tretji in četrti element, kot je arr[60] z arr[9].
Zdaj vidimo, da arr[60] > arr[9], tako da pride do zamenjave, nato pa bo matrika razvrščena v naraščajočem vrstnem redu.
| 4 | 5 | 9 | 60 |
Tako deluje razvrščanje z vstavljanjem v C, ki zlahka razvrsti element polja v naraščajočem ali padajočem vrstnem redu.
Diagram poteka razvrščanja vstavljanja
Sledi diagram poteka algoritma razvrščanja vstavljanja:
Izvajanje primera razvrščanja z vstavljanjem v C
Najprej potrebujemo zbirko elementov, ki jih je treba razvrstiti v padajočem in naraščajočem vrstnem redu, da zgradimo metodo razvrščanja z vstavljanjem v C. Za namene tega primera predpostavimo, da imamo opravka z nizom števil {5, 4, 60, 9} :
#includepraznina vstavljanje_vrsta_naraščajoče ( int arr1 [ ] , int n ) {
int jaz , j , moj_ključ ;
//zanka for se uporablja za ponavljanje vrednosti i od 1 do i
za ( jaz = 1 ; jaz < n ; jaz ++ ) {
moj_ključ = arr1 [ jaz ] ;
j = jaz - 1 ;
medtem ( j >= 0 && arr1 [ j ] > moj_ključ ) {
arr1 [ j + 1 ] = arr1 [ j ] ;
j = j - 1 ;
}
arr1 [ j + 1 ] = moj_ključ ;
}
}
praznina vstavljanje_vrsta_padajoče ( int arr2 [ ] , int m ) {
int jaz , j , moj_ključ ;
//ustvarjena je druga zanka for za ponavljanje vrednosti i od 1 do i
za ( jaz = 1 ; jaz < m ; jaz ++ ) {
moj_ključ = arr2 [ jaz ] ;
j = jaz - 1 ;
medtem ( j >= 0 && arr2 [ j ] < moj_ključ ) {
arr2 [ j + 1 ] = arr2 [ j ] ;
j = j - 1 ;
}
arr2 [ j + 1 ] = moj_ključ ;
}
}
int glavni ( ) {
//Vstavljanje-Razvrsti po padajočem vrstnem redu
int moj_arr [ ] = { 5 , 4 , 60 , 9 } ; //inicializiraj my_arr[] s štirimi vrednostmi
int m = sizeof ( moj_arr ) / sizeof ( moj_arr [ 0 ] ) ;
vstavljanje_vrsta_padajoče ( moj_arr , m ) ;
printf ( 'Razvrščeno polje v padajočem vrstnem redu: ' ) ;
za ( int jaz = 0 ; jaz < m ; jaz ++ )
printf ( '%d' , moj_arr [ jaz ] ) ;
printf ( ' \n ' ) ;
//Vstavljanje-Razvrsti v naraščajočem vrstnem redu
int n = sizeof ( moj_arr ) / sizeof ( moj_arr [ 0 ] ) ;
vstavljanje_vrsta_naraščajoče ( arr2 , n ) ;
printf ( 'Razvrščena matrika v naraščajočem vrstnem redu: ' ) ;
za ( int jaz = 0 ; jaz < n ; jaz ++ )
printf ( '%d' , moj_arr [ jaz ] ) ;
printf ( ' \n ' ) ;
vrnitev 0 ;
}
V tej kodi dve metodi insertionsort_descending() , in insertionsort_ascending() vzemite vrednosti polja moj_arr[] . Koda nato uporablja a za zanko za ponavljanje elementov matrike.
Obe funkciji pokličemo v glavni funkciji, ko razvrstita nize v padajočem in naraščajočem vrstnem redu. Nato se zanke for uporabijo za tiskanje razvrščenega niza.
Ko zaženemo ta program, je pričakovan rezultat prikazan spodaj:
Zaključek
Razvrščanje z vstavljanjem je hiter in enostaven način za razvrščanje matrike v padajočem ali naraščajočem zaporedju. Pri majhnih naborih podatkov se ta tehnika razvrščanja dobro obnese. Kot lahko vidite v zgornjem vodniku, je preprosto implementirati primer programa C za enostavno razumevanje razvrščanja vstavljanja v padajočem in naraščajočem vrstnem redu.