Kas yra įterpimo rūšiavimas C?
Rūšiavimo metodas, vadinamas įterpimo rūšiavimu, atitinka kiekvieną elementą su gretimais, kai jis kartojasi masyve. Į surūšiuotą pogrupį atitinkamoje vietoje įterpiamas mažesnis nei prieš tai buvęs elementas.
Siekdamas toliau iliustruoti, parodžiau pavyzdį, kuriame apžvelgiau keturių elementų masyvą masyve, pvz. arr[]= {5, 4, 60, 9} ir mes norime rūšiuoti šį elementą didėjančia tvarka naudodami įterpimo rūšiavimą. Šios sąveikos paaiškina visą sausą įterpimo rūšiavimo eigą:
1 iteracija
| 5 | 4 | 60 | 9 |
Dabar turime masyvą kaip arr[5, 4, 60, 9], pirmoje įterpimo rūšiavimo iteracijoje pirmiausia palyginame pirmuosius du elementus, tokius kaip 5 ir 4. Kadangi arr[5] yra > arr[4] mes juos sukeičiame, kad masyvas būtų rūšiuojamas didėjančia tvarka. Dabar masyvas bus toks:
| 4 | 5 | 60 | 9 |
2 iteracija
| 4 | 5 | 60 | 9 |
Antroje iteracijoje palyginame kitus du elementus, tokius kaip arr[5] su arr[60].
Kadangi arr[5] < arr[60], keitimas nevyksta, nes jis jau surūšiuotas didėjančia tvarka. Dabar masyvas tampa:
| 4 | 5 | 60 | 9 |
3 iteracija
| 4 | 5 | 60 | 9 |
Kaip ir trečiojoje iteracijoje, trečiąjį ir ketvirtąjį elementus, pvz., arr[60], suderiname su arr[9].
Dabar matome, kad arr[60] > arr[9] įvyksta apsikeitimas, tada masyvas bus rūšiuojamas didėjančia tvarka.
| 4 | 5 | 9 | 60 |
Taip C programoje veikia įterpimo rūšiavimas, kuris lengvai rūšiuoja masyvo elementą didėjančia arba mažėjančia tvarka.
Įterpimo rūšiavimo schema
Toliau pateikiama įterpimo rūšiavimo algoritmo schema:
Įterpimo rūšiavimo pavyzdys C
Pirmiausia mums reikia elementų rinkinio, kurį reikia rūšiuoti mažėjimo ir didėjimo tvarka, kad būtų sukurtas įterpimo rūšiavimo metodas C. Tarkime, kad šiame pavyzdyje kalbame apie skaičių masyvą {5, 4, 60, 9} :
#includetuštuma insertionsort_ascending ( tarpt arr1 [ ] , tarpt n ) {
tarpt i , j , mano_raktas ;
//for ciklas naudojamas kartoti i reikšmes nuo 1 iki i
dėl ( i = 1 ; i < n ; i ++ ) {
mano_raktas = arr1 [ i ] ;
j = i - 1 ;
kol ( j >= 0 && arr1 [ j ] > mano_raktas ) {
arr1 [ j + 1 ] = arr1 [ j ] ;
j = j - 1 ;
}
arr1 [ j + 1 ] = mano_raktas ;
}
}
tuštuma insertionsort_descending ( tarpt arr2 [ ] , tarpt m ) {
tarpt i , j , mano_raktas ;
//sukuriamas dar vienas ciklas, skirtas kartoti i reikšmes nuo 1 iki i
dėl ( i = 1 ; i < m ; i ++ ) {
mano_raktas = arr2 [ i ] ;
j = i - 1 ;
kol ( j >= 0 && arr2 [ j ] < mano_raktas ) {
arr2 [ j + 1 ] = arr2 [ j ] ;
j = j - 1 ;
}
arr2 [ j + 1 ] = mano_raktas ;
}
}
tarpt pagrindinis ( ) {
//Įterpimas-Rūšiuoti mažėjimo tvarka
tarpt mano_arr [ ] = { 5 , 4 , 60 , 9 } ; //inicijuoti my_arr[], turintį keturias reikšmes
tarpt m = dydis ( mano_arr ) / dydis ( mano_arr [ 0 ] ) ;
insertionsort_descending ( mano_arr , m ) ;
printf ( 'Rūšiuotas masyvas mažėjančia tvarka: ' ) ;
dėl ( tarpt i = 0 ; i < m ; i ++ )
printf ( '%d' , mano_arr [ i ] ) ;
printf ( “ \n “ ) ;
//Įterpimas-Rūšiuoti didėjimo tvarka
tarpt n = dydis ( mano_arr ) / dydis ( mano_arr [ 0 ] ) ;
insertionsort_ascending ( arr2 , n ) ;
printf ( 'Rūšiuotas masyvas didėjančia tvarka: ' ) ;
dėl ( tarpt i = 0 ; i < n ; i ++ )
printf ( '%d' , mano_arr [ i ] ) ;
printf ( “ \n “ ) ;
grąžinti 0 ;
}
Šiame kode yra du būdai insertionsort_descending() , ir insertionsort_ascending() paimkite masyvo reikšmes mano_arr[] . Tada kodas naudoja a už kilpą kartoti per masyvo elementus.
Mes iškviečiame abi funkcijas pagrindinėje funkcijoje, kai jos surūšiuoja masyvus mažėjančia ir didėjančia tvarka. Po to kilpos for naudojamos rūšiuotam masyvui spausdinti.
Kai vykdome šią programą, laukiama išvestis pateikiama žemiau:
Išvada
Įterpimo rūšiavimas yra greitas ir paprastas būdas rūšiuoti masyvą mažėjančia arba didėjančia seka. Mažiems duomenų rinkiniams ši rūšiavimo technika veikia gerai. Kaip matote aukščiau esančiame vadove, paprasta įdiegti C programos pavyzdį, kad būtų lengviau suprasti įterpimo rūšiavimą mažėjančia ir didėjančia tvarka.