Apa itu Insertion Sort di C?
Metode pengurutan yang disebut insertion sort mencocokkan setiap elemen dengan yang berdekatan saat iterasi melintasi array. Elemen yang lebih kecil dari yang sebelumnya dimasukkan ke dalam subarray yang diurutkan di lokasi yang sesuai.
Untuk mengilustrasikan lebih lanjut, saya telah mendemonstrasikan sebuah contoh di mana saya telah mempertimbangkan sebuah array dari empat elemen dalam sebuah array seperti arr[]= {5, 4, 60, 9} dan kami ingin mengurutkan elemen ini dalam urutan menaik dengan menggunakan insertion sort. Interaksi berikut menjelaskan dry run lengkap insertion sort:
Iterasi 1
| 5 | 4 | 60 | 9 |
Kami memiliki array sebagai arr[5, 4, 60, 9] sekarang, pada iterasi pertama dari jenis penyisipan, pertama-tama kami membandingkan dua elemen pertama seperti 5 dan 4, Karena arr[5] adalah > arr[4] jadi kami menukar mereka untuk mengurutkan array dalam urutan menaik. Sekarang, array akan menjadi:
| 4 | 5 | 60 | 9 |
Iterasi 2
| 4 | 5 | 60 | 9 |
Pada iterasi kedua, kita membandingkan dua elemen berikutnya, seperti arr[5] dengan arr[60].
Karena arr[5] < arr[60] maka pertukaran tidak terjadi karena sudah diurutkan dalam urutan menaik. Sekarang, array menjadi:
| 4 | 5 | 60 | 9 |
Iterasi 3
| 4 | 5 | 60 | 9 |
Seperti pada iterasi ketiga, kami mencocokkan elemen ketiga dan keempat seperti arr[60] dengan arr[9].
Sekarang, kita melihat bahwa arr[60] > arr[9] sehingga terjadi pertukaran, maka array akan mengurutkan dalam urutan menaik.
| 4 | 5 | 9 | 60 |
Ini adalah cara kerja pengurutan penyisipan di C yang mengurutkan elemen array dengan mudah dalam urutan naik atau turun.
Flow-Chart dari Insertion Sort
Berikut adalah flowchart dari algoritma insertion sort:
Contoh Implementasi Insertion Sort di C
Pertama-tama kita memerlukan kumpulan elemen yang perlu diurutkan dalam urutan menurun dan menaik untuk membangun metode pengurutan penyisipan di C. Asumsikan untuk tujuan contoh ini bahwa kita berurusan dengan array angka {5, 4, 60, 9} :
#termasukruang kosong insertionsort_ascending ( int arr1 [ ] , int N ) {
int Saya , J , kunci saya ;
//for loop digunakan untuk mengulang nilai i dari 1 ke i
untuk ( Saya = 1 ; Saya < N ; Saya ++ ) {
kunci saya = arr1 [ Saya ] ;
J = Saya - 1 ;
ketika ( J >= 0 && arr1 [ J ] > kunci saya ) {
arr1 [ J + 1 ] = arr1 [ J ] ;
J = J - 1 ;
}
arr1 [ J + 1 ] = kunci saya ;
}
}
ruang kosong insertionsort_descending ( int arr2 [ ] , int M ) {
int Saya , J , kunci saya ;
// loop for lainnya dibuat untuk mengiterasi nilai i dari 1 ke i
untuk ( Saya = 1 ; Saya < M ; Saya ++ ) {
kunci saya = arr2 [ Saya ] ;
J = Saya - 1 ;
ketika ( J >= 0 && arr2 [ J ] < kunci saya ) {
arr2 [ J + 1 ] = arr2 [ J ] ;
J = J - 1 ;
}
arr2 [ J + 1 ] = kunci saya ;
}
}
int utama ( ) {
//Penyisipan-Urutkan dengan urutan menurun
int my_arr [ ] = { 5 , 4 , 60 , 9 } ; //menginisialisasi sebuah my_arr[] yang memiliki empat nilai
int M = ukuran dari ( my_arr ) / ukuran dari ( my_arr [ 0 ] ) ;
insertionsort_descending ( my_arr , M ) ;
printf ( 'Array yang diurutkan dalam urutan menurun:' ) ;
untuk ( int Saya = 0 ; Saya < M ; Saya ++ )
printf ( '%D ' , my_arr [ Saya ] ) ;
printf ( ' \N ' ) ;
// Penyisipan-Urutkan dengan urutan menaik
int N = ukuran dari ( my_arr ) / ukuran dari ( my_arr [ 0 ] ) ;
insertionsort_ascending ( arr2 , N ) ;
printf ( 'Array yang diurutkan dalam urutan menaik:' ) ;
untuk ( int Saya = 0 ; Saya < N ; Saya ++ )
printf ( '%D ' , my_arr [ Saya ] ) ;
printf ( ' \N ' ) ;
kembali 0 ;
}
Dalam kode ini, dua metode insertionsort_descending() , Dan insertionsort_ascending() ambil nilai array dari my_arr[] . Kode kemudian menggunakan a untuk putaran untuk beralih melalui elemen array.
Kami memanggil kedua fungsi dalam fungsi utama setelah mereka mengurutkan array dalam urutan menurun dan menaik. Setelah itu, loop for digunakan untuk mencetak array yang diurutkan.
Ketika kami menjalankan program ini, output yang diharapkan ditempatkan di bawah ini:
Kesimpulan
Jenis penyisipan adalah cara cepat dan mudah untuk mengurutkan array dalam urutan menurun atau menaik. Untuk kumpulan data kecil, teknik penyortiran ini bekerja dengan baik. Seperti yang dapat Anda lihat dalam panduan di atas, menerapkan contoh program C untuk dengan mudah memahami urutan penyisipan dalam urutan menurun dan menaik adalah hal yang mudah.