Ano ang Insertion Sort sa C?
Ang paraan ng pag-uuri na tinatawag na insertion sort ay tumutugma sa bawat solong elemento sa mga katabi habang umuulit ito sa isang array. Isang mas maliit na elemento kaysa sa isa bago ito maipasok sa pinagsunod-sunod na subarray sa naaangkop na lokasyon.
Upang higit pang ilarawan, nagpakita ako ng isang halimbawa kung saan isinasaalang-alang ko ang isang hanay ng apat na elemento sa isang array tulad ng arr[]= {5, 4, 60, 9} at gusto naming ayusin ang elementong ito sa pataas na pagkakasunud-sunod gamit ang insertion sort. Ipinapaliwanag ng mga sumusunod na pakikipag-ugnayan ang kumpletong dry run ng insertion sort:
Pag-ulit 1
| 5 | 4 | 60 | 9 |
Mayroon kaming isang array bilang arr[5, 4, 60, 9] ngayon, sa unang pag-ulit ng pag-uuri ng pagpapasok ay inihambing muna namin ang unang dalawang elemento tulad ng 5 at 4, Dahil ang arr[5] ay > arr[4] kaya pinapalitan namin ang mga ito upang ayusin ang array sa pataas na pagkakasunud-sunod. Ngayon, ang array ay magiging:
| 4 | 5 | 60 | 9 |
Pag-ulit 2
| 4 | 5 | 60 | 9 |
Sa pangalawang pag-ulit, inihambing namin ang susunod na dalawang elemento, tulad ng arr[5] sa arr[60].
Tulad ng arr[5] < arr[60] kaya hindi nangyayari ang pagpapalit dahil ito ay nakaayos na sa pataas na pagkakasunud-sunod. Ngayon, ang array ay nagiging:
| 4 | 5 | 60 | 9 |
Pag-ulit 3
| 4 | 5 | 60 | 9 |
Tulad ng sa ikatlong pag-ulit, tinutugma namin ang ikatlo at ikaapat na elemento tulad ng arr[60] sa arr[9].
Ngayon, nakikita natin na ang arr[60] > arr[9] kaya nagaganap ang pagpapalit, pagkatapos ay mag-uuri ang array sa pataas na pagkakasunud-sunod.
| 4 | 5 | 9 | 60 |
Ito ay kung paano gumagana ang insertion sort sa C na madaling nag-uuri ng array element sa pataas o pababang pagkakasunud-sunod.
Flow-Chart ng Insertion Sort
Ang sumusunod ay ang flowchart ng algorithm ng insertion sort:
Pagpapatupad ng Halimbawa ng Insertion Sort sa C
Kailangan muna namin ng isang koleksyon ng mga elemento na kailangang pag-uri-uriin sa pababang at pataas na mga order upang mabuo ang paraan ng insertion sort sa C. Ipagpalagay na para sa mga layunin ng halimbawang ito na nakikipag-ugnayan kami sa isang hanay ng mga numero {5, 4, 60, 9} :
#includewalang bisa insertionsort_ascending ( int arr1 [ ] , int n ) {
int i , j , ang aking susi ;
//for loop ay ginagamit upang ulitin ang mga halaga ng i mula 1 hanggang i
para sa ( i = 1 ; i < n ; i ++ ) {
ang aking susi = arr1 [ i ] ;
j = i - 1 ;
habang ( j >= 0 && arr1 [ j ] > ang aking susi ) {
arr1 [ j + 1 ] = arr1 [ j ] ;
j = j - 1 ;
}
arr1 [ j + 1 ] = ang aking susi ;
}
}
walang bisa insertionsort_descending ( int arr2 [ ] , int m ) {
int i , j , ang aking susi ;
//isa pang para sa loop ay nilikha upang umulit ang mga halaga ng i mula 1 hanggang i
para sa ( i = 1 ; i < m ; i ++ ) {
ang aking susi = arr2 [ i ] ;
j = i - 1 ;
habang ( j >= 0 && arr2 [ j ] < ang aking susi ) {
arr2 [ j + 1 ] = arr2 [ j ] ;
j = j - 1 ;
}
arr2 [ j + 1 ] = ang aking susi ;
}
}
int pangunahing ( ) {
//Insertion-Uri-uri na may pababang pagkakasunod-sunod
int my_arr [ ] = { 5 , 4 , 60 , 9 } ; //initialize ang my_arr[] na may apat na value
int m = sukat ng ( my_arr ) / sukat ng ( my_arr [ 0 ] ) ;
insertionsort_descending ( my_arr , m ) ;
printf ( 'Inayos ang array sa pababang pagkakasunud-sunod: ' ) ;
para sa ( int i = 0 ; i < m ; i ++ )
printf ( '%d ' , my_arr [ i ] ) ;
printf ( ' \n ' ) ;
//Insertion-Uri-uri na may pataas na pagkakasunod-sunod
int n = sukat ng ( my_arr ) / sukat ng ( my_arr [ 0 ] ) ;
insertionsort_ascending ( arr2 , n ) ;
printf ( 'Inayos ang array sa pataas na pagkakasunud-sunod: ' ) ;
para sa ( int i = 0 ; i < n ; i ++ )
printf ( '%d ' , my_arr [ i ] ) ;
printf ( ' \n ' ) ;
bumalik 0 ;
}
Sa code na ito, dalawang pamamaraan insertionsort_descending() , at insertionsort_ascending() kunin ang mga halaga ng array ng my_arr[] . Ang code pagkatapos ay gumagamit ng a para sa loop upang umulit sa pamamagitan ng mga elemento ng array.
Tinatawag namin ang parehong mga function sa pangunahing function kapag naayos na nila ang mga array sa pababang at pataas na pagkakasunud-sunod. Pagkatapos nito, ang para sa mga loop ay ginagamit upang i-print ang pinagsunod-sunod na hanay.
Kapag pinatakbo namin ang program na ito, ang inaasahang output ay inilalagay sa ibaba:
Konklusyon
Ang insertion sort ay isang mabilis at madaling paraan upang pag-uri-uriin ang isang array sa alinman sa pababang o pataas na pagkakasunod-sunod. Para sa maliliit na dataset, mahusay na gumaganap ang diskarteng ito sa pag-uuri. Gaya ng makikita mo sa gabay sa itaas, simpleng magpatupad ng halimbawa ng isang C program para madaling maunawaan ang insertion sort sa pababang at pataas na pagkakasunod-sunod.