Mis on sisestuse sortimine C-s?
Sorteerimismeetod, mida nimetatakse sisestussortimiseks, sobitab iga üksiku elemendi külgnevatega, kui see itereerib kogu massiivi. Väiksem element kui enne, kui see sisestatakse sorteeritud alamriba sobivasse kohta.
Täiendavaks illustreerimiseks olen demonstreerinud näidet, milles käsitlesin massiivi neljast elemendist koosnevat massiivi, nagu näiteks arr[]= {5, 4, 60, 9} ja me tahame selle elemendi sortida kasvavas järjekorras, kasutades sisestussortimist. Järgmised interaktsioonid selgitavad sisestamise sortimise täielikku kuivamist:
Iteratsioon 1
| 5 | 4 | 60 | 9 |
Meil on massiiv arr[5, 4, 60, 9] nüüd, sisestussortimise esimeses iteratsioonis võrdleme esmalt kahte esimest elementi, nagu 5 ja 4. Kuna arr[5] on > arr[4] vahetame need massiivi järjestamiseks kasvavas järjekorras. Nüüd on massiiv järgmine:
| 4 | 5 | 60 | 9 |
Iteratsioon 2
| 4 | 5 | 60 | 9 |
Teises iteratsioonis võrdleme kahte järgmist elementi, näiteks arr[5] ja arr[60].
Kuna arr[5] < arr[60], siis vahetamist ei toimu, kuna see on juba järjestatud kasvavas järjekorras. Nüüd saab massiivist järgmine:
| 4 | 5 | 60 | 9 |
Iteratsioon 3
| 4 | 5 | 60 | 9 |
Nagu ka kolmandas iteratsioonis, sobitame kolmanda ja neljanda elemendi, nagu arr[60] ja arr[9].
Nüüd näeme, et arr[60] > arr[9], nii et toimub vahetus, siis sorteeritakse massiiv kasvavas järjekorras.
| 4 | 5 | 9 | 60 |
Nii töötab sisestussortimine C-s, mis sorteerib massiivi elemendid hõlpsalt kasvavas või kahanevas järjekorras.
Sisestuse sortimise vooskeem
Järgmine on sisestamise sortimise algoritmi vooskeem:
Sisestuse sortimise rakendusnäide C-s
Esmalt vajame C-s sisestuse sortimise meetodi loomiseks elementide kogu, mida tuleb sortida kahanevas ja kasvavas järjekorras. Oletagem, et selle näite puhul on tegemist arvude massiiviga. {5, 4, 60, 9} :
#includetühine insertionsort_ascending ( int arr1 [ ] , int n ) {
int i , j , minu_võti ;
//silmust kasutatakse i väärtuste itereerimiseks vahemikus 1 kuni i
jaoks ( i = 1 ; i < n ; i ++ ) {
minu_võti = arr1 [ i ] ;
j = i - 1 ;
samas ( j >= 0 && arr1 [ j ] > minu_võti ) {
arr1 [ j + 1 ] = arr1 [ j ] ;
j = j - 1 ;
}
arr1 [ j + 1 ] = minu_võti ;
}
}
tühine insertionsort_descending ( int arr2 [ ] , int m ) {
int i , j , minu_võti ;
//teine for loop luuakse i väärtuste itereerimiseks vahemikus 1 kuni i
jaoks ( i = 1 ; i < m ; i ++ ) {
minu_võti = arr2 [ i ] ;
j = i - 1 ;
samas ( j >= 0 && arr2 [ j ] < minu_võti ) {
arr2 [ j + 1 ] = arr2 [ j ] ;
j = j - 1 ;
}
arr2 [ j + 1 ] = minu_võti ;
}
}
int peamine ( ) {
//Sisestamine-Sortimine kahanevas järjekorras
int minu_arr [ ] = { 5 , 4 , 60 , 9 } ; //initsialiseeri minu_arr[], millel on neli väärtust
int m = suurus ( minu_arr ) / suurus ( minu_arr [ 0 ] ) ;
insertionsort_descending ( minu_arr , m ) ;
printf ( 'Sorditud massiiv kahanevas järjekorras: ' ) ;
jaoks ( int i = 0 ; i < m ; i ++ )
printf ( '%d' , minu_arr [ i ] ) ;
printf ( ' \n ' ) ;
//Sisestamine-Sortimine kasvavas järjekorras
int n = suurus ( minu_arr ) / suurus ( minu_arr [ 0 ] ) ;
insertionsort_ascending ( arr2 , n ) ;
printf ( 'Sorditud massiiv kasvavas järjekorras: ' ) ;
jaoks ( int i = 0 ; i < n ; i ++ )
printf ( '%d' , minu_arr [ i ] ) ;
printf ( ' \n ' ) ;
tagasi 0 ;
}
Selles koodis on kaks meetodit insertionsort_descending() , ja insertionsort_ascending() võta massiivi väärtused minu_arr[] . Seejärel kasutab kood a silmuse jaoks massiivi elementide kordamiseks.
Me kutsume põhifunktsioonis mõlemat funktsiooni, kui nad on sorteerinud massiivid kahanevas ja kasvavas järjekorras. Pärast seda kasutatakse sorditud massiivi printimiseks silmust for.
Selle programmi käivitamisel paigutatakse oodatav väljund allpool:
Järeldus
Sisestussortimine on kiire ja lihtne viis massiivi sortimiseks kas kahanevas või kasvavas järjestuses. Väikeste andmekogumite puhul toimib see sortimistehnika hästi. Nagu näete ülaltoodud juhendist, on lihtne rakendada C-programmi näidet, et hõlpsasti mõista sisestamise sortimist nii kahanevas kui ka kasvavas järjekorras.