Isaalang-alang ang mga sumusunod na numero:
50 60 30 10 80 70 20 40
Kung ang listahang ito ay pinagsunod-sunod sa pataas na pagkakasunud-sunod, ito ay magiging:
10 20 30 40 50 60 70 80
Kung ito ay pinagsunod-sunod sa pababang pagkakasunud-sunod, ito ay magiging:
80 70 60 50 40 30 20 10
Ang insertion sort ay isang algorithm ng pag-uuri na ginagamit upang pag-uri-uriin ang listahan sa pataas na pagkakasunud-sunod o sa pababang pagkakasunud-sunod. Ang artikulong ito ay tumatalakay lamang sa pag-uuri sa pataas na pagkakasunud-sunod. Ang pag-uuri sa pababang pagkakasunud-sunod ay sumusunod sa parehong lohika na ibinigay sa dokumentong ito. Ang layunin ng artikulong ito ay ipaliwanag ang insertion sort. Ginagawa ang programming sa sumusunod na halimbawa sa C. Ang insertion sort ay ipinaliwanag dito gamit ang isang array.
Algorithm para sa Insertion Sort
Isang hindi pinagsunod-sunod na listahan ang ibinigay. Ang layunin ay pag-uri-uriin ang listahan sa pataas na pagkakasunud-sunod gamit ang parehong listahan. Ang pag-uuri ng isang hindi naayos na array gamit ang parehong array ay sinasabing pag-uuri sa lugar. Ginagamit dito ang zero based indexing. Ang mga hakbang ay ang mga sumusunod:
-
- Ang listahan ay ini-scan mula sa simula.
- Habang nagpapatuloy ang pag-scan, ang anumang numerong mas mababa sa hinalinhan nito ay ipinagpapalit sa hinalinhan nito.
- Ang pagpapalit na ito ay nagpapatuloy sa listahan, hanggang sa hindi na posible na magpalit.
- Kapag ang pag-scan ay umabot sa dulo, ang pag-uuri ay kumpleto na.
Insertion Sort Illustration
Kapag nakikitungo sa pagiging kumplikado ng oras, ito ang pinakamasamang kaso na karaniwang isinasaalang-alang. Ang pinakamasamang pagsasaayos para sa nakaraang listahan ay:
80 70 60 50 40 30 20 10
Mayroong walong elemento na may mga index mula zero hanggang 7.
Sa index zero, ang pag-scan ay napupunta sa 80. Ito ay isang paggalaw. Ang isang kilusang ito ay isang operasyon. Mayroong kabuuang isang operasyon sa ngayon (isang paggalaw, walang paghahambing, at walang swap). Ang resulta ay:
| 80 70 60 50 40 30 20 10
Sa index isa, mayroong isang paggalaw sa 70. 70 ay inihambing sa 80. 70 at 80 ay ipinagpalit. Ang isang kilusan ay isang operasyon. Ang isang paghahambing ay isang operasyon din. Ang isang swap ay isang operasyon din. Ang seksyong ito ay nagbibigay ng tatlong operasyon. Mayroong kabuuang apat na operasyon sa ngayon (1 + 3 = 4). Ang resulta ay ang mga sumusunod:
70 | 80 60 50 40 30 20 10
Sa index two, mayroong isang paggalaw sa 60. 60 ay inihambing sa 80, pagkatapos ay 60 at 80 ay ipinagpalit. Ang 60 ay inihambing sa 70, pagkatapos ay 60 at 70 ay ipinagpalit. Ang isang kilusan ay isang operasyon. Ang dalawang paghahambing ay dalawang operasyon. Ang dalawang swap ay dalawang operasyon. Ang seksyong ito ay nagbibigay ng limang operasyon. Mayroong kabuuang siyam na operasyon sa ngayon (4 + 5 = 9). Ang resulta ay ang mga sumusunod:
60 70 | 80 50 40 30 20 10
Sa index three, mayroong isang paggalaw sa 50. 50 ay inihambing sa 80, pagkatapos ay 50 at 80 ay ipinagpalit. Ang 50 ay inihambing sa 70, pagkatapos ay 50 at 70 ay ipinagpalit. Ang 50 ay inihambing sa 60, pagkatapos ay 50 at 60 ay ipinagpalit. Ang isang kilusan ay isang operasyon. Tatlong paghahambing ay tatlong operasyon. Ang tatlong swap ay tatlong operasyon. Ang seksyong ito ay nagbibigay ng pitong operasyon. Mayroong kabuuang labing-anim na operasyon sa ngayon (9 + 7 = 16). Ang resulta ay ang mga sumusunod:
50 60 70 | 80 40 30 20 10
Sa index na apat, mayroong isang paggalaw sa 40. 40 ay inihambing sa 80, pagkatapos ay 40 at 80 ay ipinagpalit. Ang 40 ay inihambing sa 70, pagkatapos ay 40 at 70 ay ipinagpalit. Ang 40 ay inihambing sa 60, pagkatapos ay ang 40 at 60 ay ipinagpalit. Ang 40 ay inihambing sa 50, pagkatapos ay ang 40 at 50 ay ipinagpalit. Ang isang kilusan ay isang operasyon. Apat na paghahambing ay apat na operasyon. Apat na swap ay apat na operasyon. Ang seksyong ito ay nagbibigay ng siyam na operasyon. Mayroong kabuuang dalawampu't limang operasyon sa ngayon (16 + 9 = 25). Ang resulta ay ang mga sumusunod:
40 50 60 70 80 | 30 20 10
Sa index five, mayroong isang paggalaw sa 30. 30 ay inihambing sa 80, pagkatapos ay 30 at 80 ay ipinagpalit. Ang 30 ay inihambing sa 70, pagkatapos ay 30 at 70 ay ipinagpalit. Ang 30 ay inihambing sa 60, pagkatapos ay ang 30 at 60 ay ipinagpalit. Ang 30 ay inihambing sa 50, pagkatapos ay 30 at 50 ay ipinagpalit. Ang 30 ay ikinumpara sa 40, pagkatapos ay 30 at 40 ang ipinagpalit. Ang isang kilusan ay isang operasyon. Limang paghahambing ay limang operasyon. Ang limang swap ay limang operasyon. Ang seksyong ito ay nagbibigay ng labing-isang operasyon. Mayroong kabuuang tatlumpu't anim na operasyon sa ngayon (25 + 11 = 36). Ang resulta ay ang mga sumusunod:
30 40 50 60 70 80 | 20 10
Sa index six, mayroong isang paggalaw sa 20. 20 ay inihambing sa 80, pagkatapos ay 20 at 80 ay ipinagpalit. Ang 20 ay inihambing sa 70, pagkatapos ay 20 at 70 ay ipinagpalit. Ang 20 ay inihambing sa 60, pagkatapos ay 20 at 60 ay ipinagpalit. Ang 20 ay inihambing sa 50, pagkatapos ay 20 at 50 ay ipinagpalit. Ang 20 ay inihambing sa 40, pagkatapos ay 20 at 40 ay ipinagpalit. Ang 20 ay inihambing sa 30, pagkatapos ay 20 at 30 ay ipinagpalit. Ang isang kilusan ay isang operasyon. Ang anim na paghahambing ay anim na operasyon. Ang anim na swap ay anim na operasyon. Ang seksyong ito ay nagbibigay ng labintatlong operasyon. Mayroong kabuuang apatnapu't siyam na operasyon sa ngayon (36 + 13 = 49). Ang resulta ay ang mga sumusunod:
20 30 40 50 60 70 80 | 10
Sa index pito, mayroong isang paggalaw sa 10. 10 ay inihambing sa 80, pagkatapos ay 10 at 80 ay ipinagpalit. Ang 10 ay inihambing sa 70, pagkatapos ay ang 10 at 70 ay ipinagpalit. Ang 10 ay inihambing sa 60, pagkatapos ay 10 at 60 ay ipinagpalit. Ang 10 ay inihambing sa 50, pagkatapos ay ang 10 at 50 ay ipinagpalit. Ang 10 ay inihambing sa 30, pagkatapos ay ang 10 at 40 ay ipinagpalit. Ang 10 ay inihambing sa 30, pagkatapos ay ang 10 at 30 ay ipinagpalit. Ang 10 ay inihambing sa 20, pagkatapos ay ang 10 at 20 ay ipinagpalit. Ang isang kilusan ay isang operasyon. Ang pitong paghahambing ay pitong operasyon. Ang pitong swap ay pitong operasyon. Ang seksyong ito ay nagbibigay ng labinlimang operasyon. Mayroong kabuuang animnapu't apat na operasyon sa ngayon (49 + 15 = 64). Ang resulta ay ang mga sumusunod:
10 20 30 40 50 60 70 80 10 |
Tapos na ang trabaho! 64 na operasyon ang kasangkot.
64 = 8 x 8 = 8 dalawa
Pagiging Kumplikado ng Oras para sa Insertion Sort
Kung mayroong n elemento na pag-uuri-uriin gamit ang Insertion Sort, ang maximum na bilang ng mga posibleng operasyon ay n2, gaya ng ipinakita dati. Ang pagiging kumplikado ng Insertion Sort Time ay:
O(n dalawa )
Ito ay gumagamit ng Big-O notation. Ang Big-O notation ay nagsisimula sa O sa uppercase, na sinusundan ng mga panaklong. Sa loob ng mga panaklong ay ang expression para sa maximum na posibleng bilang ng mga operasyon.
Pag-coding sa C
Sa pinakadulo simula ng pag-scan, hindi mababago ng unang elemento ang posisyon nito. Ang programa ay mahalagang ang mga sumusunod:
#includevoid insertionSort ( int A [ ] , int N ) {
para sa ( int i = 0 ; i < N; i++ ) {
int j = i;
habang ( A [ j ] < A [ j- 1 ] && j- 1 > = 0 ) {
int temp = A [ j ] ; A [ j ] = A [ j- 1 ] ; A [ j- 1 ] = temp; // magpalit
j--;
}
}
}
Ang kahulugan ng insertionSort() function ay gumagamit ng algorithm tulad ng inilarawan. Tandaan ang mga kondisyon para sa while-loop. Ang isang angkop na pangunahing function ng C para sa program na ito ay:
{
int n = 8 ;
int A [ ] = { limampu , 60 , 30 , 10 , 80 , 70 , dalawampu , 40 } ;
insertionSort ( A, n ) ;
para sa ( int i = 0 ; i < n; i++ ) {
printf ( '%i ' , A [ i ] ) ;
}
printf ( ' \n ' ) ;
bumalik 0 ;
}
Konklusyon
Ang pagiging kumplikado ng oras para sa Insertion Sort ay ibinibigay bilang:
O(n dalawa )
Maaaring narinig ng mambabasa ang tungkol sa mas masahol na kaso ng pagiging kumplikado ng oras, average na kaso ng pagiging kumplikado ng oras at pinakamahusay na kaso ng pagiging kumplikado ng oras. Ang mga variation na ito ng Insertion Sort Time Complexity ay tinalakay sa susunod na artikulo sa aming website.