Mahalagang Pagkakaiba – Insertion Sort vs Selection Sort
Ang Insertion sort at selection sort ay dalawang algorithm ng pag-uuri na ginagamit upang pagbukud-bukurin ang isang koleksyon ng data. Minsan ito ay kinakailangan upang ayusin ang data sa isang tiyak na pagkakasunud-sunod. Ang mga algorithm ng pag-uuri ay mga mekanismo upang pagbukud-bukurin ang isang set ng data. Sa pag-uuri, ang data ay nakaayos ayon sa isang numerical o isang lexicographical order. Kung maayos na inayos ang data, magiging madali ang paghahanap ng data nang mas mabilis. Kung ang mga numero ng telepono sa isang direktoryo ng telepono ay wala sa isang nakaayos na paraan, kung gayon ay magiging mahirap na makahanap ng isang partikular na numero ng telepono. Sa parehong paraan, kung ang mga salita sa diksyunaryo ay hindi nakaayos sa alpabetikong pagkakasunud-sunod, magiging napakahirap na makahanap ng mga salita. Samakatuwid, ang pag-uuri ay kapaki-pakinabang sa pang-araw-araw na buhay. Sa Computer Science, mayroong mga algorithm ng pag-uuri upang ayusin ang isang koleksyon ng data. Dalawang ganoong algorithm ang insertion sort at selection sort. Ang insertion sort ay ang sorting algorithm na nag-uuri ng array sa pamamagitan ng paglilipat ng mga elemento nang paisa-isa. Ang selection sort ay ang sorting algorithm na nakakahanap ng pinakamaliit na elemento sa array at ipinagpapalit ang elemento sa unang posisyon, pagkatapos ay hanapin ang pangalawang pinakamaliit na elemento at palitan ito ng elemento sa pangalawang posisyon at ipagpatuloy ang proseso hanggang sa ang buong array ay maiayos.. Ang pangunahing pagkakaiba sa pagitan ng insertion sort at selection sort ay ang insertion sort ay naghahambing ng dalawang elemento sa isang pagkakataon habang pinipili ng selection sort ang minimum na elemento mula sa buong array at pinag-uuri ito.
Ano ang Insertion Sort?
Ang Insertion sort ay isang in-place na paghahambing na nakabatay sa pag-uuri algorithm. Sa pamamaraang ito, hinanap ang array nang hakbang-hakbang. Ang mga hindi na-sort na item ay inilipat at ipinapasok sa pinagsunod-sunod na sublist ng array. Maaaring ipaliwanag ang insertion sort algorithm gamit ang sumusunod na halimbawa.
Halimbawa, kunin ang paunang array bilang 77, 33, 44, 11, 88. Sa algorithm ng pag-uuri na ito, ang unang hakbang ay piliin ang kasalukuyang elemento.
Ang kasalukuyang elemento ay 77. Ang kasalukuyang elemento ay inihambing sa lahat ng elemento sa kaliwang bahagi. Ang 77, ay ang unang elemento at walang mga elemento sa kaliwang bahagi. Ang index ng kasalukuyang posisyon ay 0.
Pagkatapos, ang index ng kasalukuyang posisyon ay dinadagdagan ng 1. Ngayon ang index ay 1, at ang kasalukuyang elemento ay 33. Kapag inihambing ito sa elemento sa kaliwa, ito ay mas maliit sa 77. Pagkatapos ang parehong mga halagang ito ay pinagpalit. Ngayon, 33 ang nasa index 0, at 77 ang nasa index1.
Ngayon ang array ay 33, 77, 44, 11, 88.
Muli, ang index ay nadagdagan. Ang index ay 2, at ang kasalukuyang elemento ay 44. Ito ay inihambing sa mga elemento sa kaliwang bahagi. Ang 44 ay mas mababa sa 77. Kaya ang dalawang halagang iyon ay pinagpalit. Ngayon ang array ay 33, 44, 77, 11, 88. Kinakailangang ihambing ang lahat ng elemento sa kaliwa. Kaya, ang 44 ay inihambing sa 33. Ang 33 ay mas maliit sa 44. Kaya't ang mga elementong iyon ay hindi kailangang palitan.
Ngayon ang array ay 33, 44, 77, 11, 88.
Muli, ang index ay nadagdagan. Ang index ay 3, at ang kasalukuyang elemento ay 11. Ito ay inihambing sa lahat ng mga elemento sa kaliwa. Ang 11 ay mas mababa sa 77, kaya ang dalawang iyon ay pinagpalit. Ngayon ang array ay 33, 44, 11, 77, 88. Kapag inihambing ang 11 at 44, ang 11 ay mas mababa sa 44. Kaya ang dalawang iyon ay pinagpalit. Ngayon ang mga arrays ay 33, 11, 44, 77, 88. Muli, ang 11 ay inihambing sa 33. Ang 11 ay mas mababa sa 33, kaya ang dalawang value na iyon ay pinagpalit.
Ngayon ang array ay 11, 33, 44, 77, 88.
Ang pagdaragdag sa index ay gagawing 4 ang index. Ang halaga ay 88. Mas mataas ito sa 77. Kaya, hindi na kailangang magpalit. Panghuli, ang pinagsunod-sunod na array ay 11, 33, 44, 77, 88.
Figure 01: Halimbawa ng insertion sort
Ang pagpapatupad ng insertion sort ay tulad ng nasa itaas. Ang paunang array ay 77, 33, 44, 11, 88. Pagkatapos ng pag-uuri, binibigyan nito ang output na 11, 33, 44, 77, 88.
Ano ang Selection Sort?
Ang Selection sort ay isang in-place na paghahambing-based na algorithm ng pag-uuri. Ang mga array ay nahahati sa mga seksyon. Ang pinagsunod-sunod na bahagi ay nasa kaliwang dulo. Ang hindi naayos na bahagi ay nasa kanang dulo. Una, dapat mahanap ang pinakamaliit na halaga. Pagkatapos ay pinapalitan ito ng kaliwang elemento. Ngayon ang elementong iyon ay nasa sorted array. Ang prosesong ito ay patuloy na naglilipat ng hindi naayos na hangganan ng array mula sa isang elemento patungo sa kanan. Maaaring ipaliwanag ang algorithm ng pag-uuri ng pagpili gamit ang sumusunod na halimbawa.
Halimbawa, kunin ang paunang array bilang 77, 33, 44, 11, 88, 22. Sa algorithm ng pag-uuri na ito, makikita ang pinakamaliit sa array. Ang pinakamaliit na elemento ay 11. Ito ay pinapalitan ng elemento sa 0 index ng array.
Ngayon ang array ay 11, 33, 44, 77, 88, 22.
Ang pinakamaliit na elemento ay nasa index na 0, kaya 11 ang pinagsunod-sunod na ngayon. Mula sa iba pang elemento, ang pinakamaliit ay 22. Pinapalitan ito ng 1st index element.
Ngayon ang array ay 11, 22, 44, 77, 88, 33.
Nakaayos na ang mga elemento 11 at 22. Mula sa iba, ang pinakamaliit na value ay 33. Pinapalitan ito ng 2nd index element.
Ngayon ang array ay 11, 22, 33, 77, 88, 44.
Nakaayos na ang mga elemento 11, 22 at 33. Mula sa iba, ang pinakamaliit na value ay 44. Pinapalitan ito ng 3rd index element.
Ngayon ang array ay 11, 22, 33, 44, 88, 66.
Ang mga elementong 11, 22, 33, 44 ay nakaayos na. Ang natitirang mga elemento ay 88 at 66. Ang elemento 66 ay pinapalitan ng 4ika na elemento ng index.
Ngayon ang array ay 11, 22, 33, 44, 66, 88.
Ito ang pinagsunod-sunod na array gamit ang selection sort algorithm.
Figure 02: Halimbawa ng Selection Sort
Ang pagpapatupad ng insertion sort ay tulad ng nasa itaas. Ang paunang array ay 77, 33, 44, 11, 88. Pagkatapos ng pag-uuri, binibigyan nito ang output na 11, 33, 44, 77, 88.
Ano ang Pagkakatulad sa pagitan ng Insertion Sort at Selection Sort?
Ang Insertion Sort at Selection Sort ay mga algorithm sa pag-uuri
Ano ang Pagkakaiba sa pagitan ng Insertion Sort at Selection Sort?
Insertion Sort vs Selection Sort |
|
| Ang insertion sort ay ang sorting algorithm na nag-uuri ng array sa pamamagitan ng paglilipat ng mga elemento nang paisa-isa. | Ang selection sort ay ang sorting algorithm na nakakahanap ng pinakamaliit na elemento sa array at ipinagpapalit ang elemento sa unang posisyon, pagkatapos ay hanapin ang pangalawang pinakamaliit na elemento at palitan ito ng elemento sa pangalawang posisyon at ipagpatuloy ang proseso hanggang ang buong array ay pinagsunod-sunod. |
| Proseso | |
| Ang insertion sort ay ang pag-uri-uriin ang sub list sa pamamagitan ng paghahambing ng dalawang elemento hanggang sa ang buong array ay pag-uri-uriin. | Pinipili ng selection sort ang minimum na elemento at pinapalitan ito ng unang posisyon, piliin muli ang minimum para sa natitira at palitan ito sa pangalawang posisyon at ipagpatuloy ang prosesong ito hanggang sa katapusan. |
| Katatagan | |
| Insertion sort ay isang stable sorting algorithm. | Ang pag-uuri ng seleksyon ay hindi isang matatag na algorithm ng pag-uuri. |
Buod – Insertion Sort vs Selection Sort
Minsan kinakailangan na pagbukud-bukurin ang data. Sa Computer Science, may mga algorithm para pagbukud-bukurin ang data. Tinalakay ng artikulong ito ang dalawang algorithm ng pag-uuri na insertion sort at selection sort. Ang insertion sort ay ang sorting algorithm na nag-uuri ng array sa pamamagitan ng paglilipat ng mga elemento nang paisa-isa. Ang selection sort ay ang sorting algorithm na nakakahanap ng pinakamaliit na elemento sa array at ipinagpapalit ang elemento sa unang posisyon, pagkatapos ay hanapin ang pangalawang pinakamaliit na elemento at palitan ito ng elemento sa pangalawang posisyon at ipagpatuloy ang proseso hanggang sa ang buong array ay maiayos.. Ang pagkakaiba sa pagitan ng insertion sort at selection sort ay ang insertion sort ay naghahambing ng dalawang elemento sa isang pagkakataon habang pinipili ng selection sort ang pinakamababang elemento mula sa buong array at pinagbubukod-bukod ito.
I-download ang PDF ng Insertion Sort vs Selection Sort
Maaari mong i-download ang PDF na bersyon ng artikulong ito at gamitin ito para sa offline na layunin ayon sa tala ng pagsipi. Paki-download ang bersyon ng PDF dito: Pagkakaiba sa pagitan ng Insertion Sort at Selection Sort
