Apakah Isih Sisipan dalam C?
Kaedah pengisihan yang dipanggil isihan sisipan memadankan setiap elemen tunggal dengan elemen yang bersebelahan kerana ia berulang merentasi tatasusunan. Elemen yang lebih kecil daripada elemen sebelum ia dimasukkan ke dalam subarray yang diisih di lokasi yang sesuai.
Untuk menggambarkan lebih lanjut, saya telah menunjukkan contoh di mana saya telah mempertimbangkan tatasusunan empat elemen dalam tatasusunan seperti arr[]= {5, 4, 60, 9} dan kami ingin mengisih elemen ini dalam tertib menaik dengan menggunakan isihan sisipan. Interaksi berikut menerangkan larian kering lengkap jenis sisipan:
Lelaran 1
| 5 | 4 | 60 | 9 |
Kami mempunyai tatasusunan sebagai arr[5, 4, 60, 9] sekarang, dalam lelaran pertama isihan sisipan kami mula-mula membandingkan dua elemen pertama seperti 5 dan 4, Oleh kerana arr[5] ialah > arr[4] jadi kami menukarnya untuk mengisih tatasusunan dalam tertib menaik. Sekarang, tatasusunan akan menjadi:
| 4 | 5 | 60 | 9 |
Lelaran 2
| 4 | 5 | 60 | 9 |
Dalam lelaran kedua, kami membandingkan dua elemen seterusnya, seperti arr[5] dengan arr[60].
Oleh kerana arr[5] < arr[60] jadi pertukaran tidak berlaku kerana ia telah diisih dalam tertib menaik. Sekarang, tatasusunan menjadi:
| 4 | 5 | 60 | 9 |
Lelaran 3
| 4 | 5 | 60 | 9 |
Seperti dalam lelaran ketiga, kami memadankan elemen ketiga dan keempat seperti arr[60] dengan arr[9].
Sekarang, kita melihat bahawa arr[60] > arr[9] jadi pertukaran berlaku, maka tatasusunan akan mengisih dalam tertib menaik.
| 4 | 5 | 9 | 60 |
Beginilah cara isihan sisipan berfungsi dalam C yang menyusun elemen tatasusunan dengan mudah dalam tertib menaik atau menurun.
Carta Aliran Isih Sisipan
Berikut ialah carta alir algoritma jenis sisipan:
Melaksanakan Contoh Isih Sisipan dalam C
Kami mula-mula memerlukan koleksi elemen yang perlu diisih dalam tertib menurun dan menaik untuk membina kaedah isihan sisipan dalam C. Anggapkan untuk tujuan contoh ini bahawa kita sedang berurusan dengan tatasusunan nombor {5, 4, 60, 9} :
#includebatal insertionsort_ascending ( int arr1 [ ] , int n ) {
int i , j , kunci_saya ;
//for loop digunakan untuk mengulangi nilai i dari 1 hingga i
untuk ( i = 1 ; i < n ; i ++ ) {
kunci_saya = arr1 [ i ] ;
j = i - 1 ;
sementara ( j >= 0 && arr1 [ j ] > kunci_saya ) {
arr1 [ j + 1 ] = arr1 [ j ] ;
j = j - 1 ;
}
arr1 [ j + 1 ] = kunci_saya ;
}
}
batal insertionsort_descending ( int arr2 [ ] , int m ) {
int i , j , kunci_saya ;
//satu lagi untuk gelung dicipta untuk mengulangi nilai i dari 1 hingga i
untuk ( i = 1 ; i < m ; i ++ ) {
kunci_saya = arr2 [ i ] ;
j = i - 1 ;
sementara ( j >= 0 && arr2 [ j ] < kunci_saya ) {
arr2 [ j + 1 ] = arr2 [ j ] ;
j = j - 1 ;
}
arr2 [ j + 1 ] = kunci_saya ;
}
}
int utama ( ) {
//Sisipan-Isih dengan tertib menurun
int my_arr [ ] = { 5 , 4 , 60 , 9 } ; //memulakan my_arr[] yang mempunyai empat nilai
int m = saiz ( my_arr ) / saiz ( my_arr [ 0 ] ) ;
insertionsort_descending ( my_arr , m ) ;
printf ( 'Isih tatasusunan dalam tertib menurun: ' ) ;
untuk ( int i = 0 ; i < m ; i ++ )
printf ( '%d ' , my_arr [ i ] ) ;
printf ( ' \n ' ) ;
//Sisipan-Isih dengan tertib menaik
int n = saiz ( my_arr ) / saiz ( my_arr [ 0 ] ) ;
insertionsort_ascending ( arr2 , n ) ;
printf ( 'Susun atur disusun dalam tertib menaik: ' ) ;
untuk ( int i = 0 ; i < n ; i ++ )
printf ( '%d ' , my_arr [ i ] ) ;
printf ( ' \n ' ) ;
kembali 0 ;
}
Dalam kod ini, dua kaedah insertionsort_descending() , dan insertionsort_ascending() ambil nilai tatasusunan bagi my_arr[] . Kod itu kemudiannya menggunakan a untuk gelung untuk lelaran melalui elemen tatasusunan.
Kami memanggil kedua-dua fungsi dalam fungsi utama apabila mereka telah mengisih tatasusunan dalam tertib menurun dan menaik. Selepas itu, gelung for digunakan untuk mencetak tatasusunan yang diisih.
Apabila kami menjalankan program ini, output yang dijangkakan diletakkan di bawah:
Kesimpulan
Isihan sisipan ialah cara yang cepat dan mudah untuk mengisih tatasusunan sama ada dalam turutan menurun atau menaik. Untuk set data kecil, teknik pengisihan ini berfungsi dengan baik. Seperti yang anda lihat dalam panduan di atas, adalah mudah untuk melaksanakan contoh program C untuk memahami dengan mudah isihan sisipan dalam tertib menurun dan juga menaik.