May ilang pangunahing algorithm para sa paglutas ng problema sa pag-uuri ng array. Isa sa pinakasikat sa kanila ay insertion sort. Dahil sa kalinawan at pagiging simple nito, ngunit mababa ang kahusayan, ang pamamaraang ito ay pangunahing ginagamit sa pagtuturo ng programming. Binibigyang-daan ka nitong maunawaan ang mga pangunahing mekanismo ng pag-uuri.
Paglalarawan ng algorithm
Ang esensya ng insertion sort algorithm ay ang isang maayos na nakaayos na segment ay nabuo sa loob ng paunang array. Ang bawat elemento ay inihambing isa-isa sa may check na bahagi at ipinasok sa tamang lugar. Kaya, pagkatapos ng pag-ulit sa lahat ng mga elemento, pumila sila sa tamang pagkakasunod-sunod.
Ang pagkakasunud-sunod ng pagpili ng mga elemento ay maaaring anuman, maaari silang piliin nang basta-basta o ayon sa ilang algorithm. Kadalasan, ang sequential enumeration ay ginagamit mula sa simula ng array, kung saan nabuo ang isang ordered segment.
Maaaring ganito ang simula ng pag-uuri:
- Kunin ang unang elemento ng array.
- Dahil walang maihahambing dito, kunin ang mismong elemento ayon sa pagkakasunud-sunodpagkakasunod-sunod.
- Pumunta sa pangalawang item.
- Ihambing ito sa una batay sa panuntunan sa pag-uuri.
- Kung kinakailangan, magpalit ng mga elemento sa mga lugar.
- Kunin ang unang dalawang elemento bilang isang pagkakasunod-sunod.
- Pumunta sa ikatlong item.
- Ihambing ito sa pangalawa, palitan kung kinakailangan.
- Kung nagawa na ang kapalit, ihambing ito sa una.
- Kumuha ng tatlong elemento bilang nakaayos na pagkakasunod-sunod.
At iba pa hanggang sa katapusan ng orihinal na array.
Real life insertion sort
Para sa kalinawan, sulit na magbigay ng halimbawa kung paano ginagamit ang mekanismo ng pag-uuri na ito sa pang-araw-araw na buhay.
Kumuha, halimbawa, ng wallet. Daan-daan, limang-daan, at libong-dolyar na perang papel ang nagkakagulo sa kompartimento ng banknote. Ito ay isang gulo, sa gayong hodgepodge mahirap mahanap agad ang tamang piraso ng papel. Dapat pagbukud-bukurin ang hanay ng mga banknote.
Ang pinakauna ay isang banknote na 1000 rubles, at kaagad pagkatapos nito - 100. Kumuha kami ng isang daan at inilalagay ito sa harap. Ang pangatlo sa isang hilera ay 500 rubles, ang nararapat na lugar para dito ay nasa pagitan ng isang daan at isang libo.
Sa parehong paraan, pinag-uuri namin ang mga natanggap na card kapag naglalaro ng "Fool" para mas madaling i-navigate ang mga ito.
Mga function ng operator at helper
Ang paraan ng insertion sort ay kumukuha bilang input ng isang paunang array na pagbukud-bukurin, isang function ng paghahambing, at, kung kinakailangan, isang function na tumutukoy sa panuntunan para sa pag-enumerate ng mga elemento. Kadalasang ginagamit sa halipregular na loop statement.
Ang unang elemento ay mismong isang ordered set, kaya ang paghahambing ay magsisimula sa pangalawa.
Madalas na gumagamit ang algorithm ng function na helper para makipagpalitan ng dalawang value (swap). Gumagamit ito ng karagdagang pansamantalang variable, na kumukonsumo ng memory at medyo nagpapabagal sa code.
Ang isang alternatibo ay ang mass shift ng isang pangkat ng mga elemento at pagkatapos ay ipasok ang kasalukuyang isa sa libreng espasyo. Sa kasong ito, ang paglipat sa susunod na elemento ay nangyayari kapag ang paghahambing ay nagbigay ng positibong resulta, na nagsasaad ng tamang pagkakasunud-sunod.
Mga halimbawa ng pagpapatupad
Ang partikular na pagpapatupad ay higit na nakadepende sa programming language na ginamit, syntax at istruktura nito.
Pagpapatupad ng Classic C gamit ang isang pansamantalang variable upang makipagpalitan ng mga halaga:
int i, j, temp; para sa (i=1; i =0; j--) { if (array[j] < temp) break; array[j + 1]=array[j]; array [j]=temp; } }
Pagpapatupad ng PHP:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Dito, una, lahat ng elementong hindi tumutugma sa kundisyon ng pag-uuri ay inililipat sa kanan, at pagkatapos ay ipinapasok ang kasalukuyang elemento sa libreng espasyo.
Java code gamit ang while loop:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Ang pangkalahatang kahulugan ng code ay nananatiling hindi nagbabago: ang bawat elemento ng array ay sunud-sunod na inihahambing sa mga nauna at ipinagpalit sa kanila kung kinakailangan.
Tinantyang tagal ng pagtakbo
Malinaw, sa pinakamagandang kaso, ang input ng algorithm ay isang array na naayos na sa tamang paraan. Sa sitwasyong ito, kailangan lang suriin ng algorithm ang bawat elemento upang matiyak na nasa tamang lugar ito nang hindi gumagawa ng mga palitan. Kaya, ang oras ng pagpapatakbo ay direktang magdedepende sa haba ng orihinal na array O(n).
Ang pinakamasamang case input ay isang array na pinagsunod-sunod sa reverse order. Mangangailangan ito ng malaking bilang ng mga permutasyon, ang pagpapaandar ng runtime ay magdedepende sa bilang ng mga elementong nakakuwadrado.
Ang eksaktong bilang ng mga permutasyon para sa isang ganap na hindi nakaayos na array ay maaaring kalkulahin gamit ang formula:
n(n-1)/2
kung saan ang n ay ang haba ng orihinal na array. Kaya, aabutin ng 4950 permutation para ayusin ang 100 elemento sa tamang pagkakasunud-sunod.
Ang paraan ng pagpapasok ay napakahusay para sa pag-uuri ng maliliit o bahagyang pinagsunod-sunod na mga array. Gayunpaman, hindi inirerekomenda na ilapat ito sa lahat ng dako dahil sa mataas na pagiging kumplikado ng mga kalkulasyon.
Ginagamit ang algorithm bilang pantulong sa maraming iba pang mas kumplikadong paraan ng pag-uuri.
Pagbukud-bukurin ang mga katumbas na halaga
Ang insertion algorithm ay nabibilang sa tinatawag na stable sorts. Ibig sabihin,na hindi nito pinapalitan ang magkatulad na mga elemento, ngunit pinapanatili ang kanilang orihinal na pagkakasunud-sunod. Ang stability index sa maraming pagkakataon ay mahalaga para sa tamang pag-order.
Ang nasa itaas ay isang magandang visual na halimbawa ng insertion sort sa isang sayaw.
