Ekzistojnë disa algoritme bazë për zgjidhjen e problemit të renditjes së një grupi. Një nga më të famshmit midis tyre është lloji i futjes. Për shkak të qartësisë dhe thjeshtësisë, por efikasitetit të ulët, kjo metodë përdoret kryesisht në mësimdhënien e programimit. Kjo ju lejon të kuptoni mekanizmat bazë të renditjes.
Përshkrimi i algoritmit
Thelbi i algoritmit të renditjes së futjes është që brenda grupit fillestar të formohet një segment i renditur siç duhet. Çdo element krahasohet një nga një me pjesën e kontrolluar dhe futet në vendin e duhur. Kështu, pas përsëritjes nëpër të gjithë elementët, ata rreshtohen në rendin e duhur.
Radha e zgjedhjes së elementeve mund të jetë çdo, ato mund të zgjidhen në mënyrë arbitrare ose sipas ndonjë algoritmi. Më shpesh, numërimi sekuencial përdoret nga fillimi i grupit, ku formohet një segment i renditur.
Fillimi i renditjes mund të duket kështu:
- Merr elementin e parë të grupit.
- Meqenëse nuk ka asgjë për t'u krahasuar me të, merre vetë elementin siç është porositursekuencë.
- Shko te artikulli i dytë.
- Krahasojeni me të parën bazuar në rregullin e renditjes.
- Nëse është e nevojshme, ndërroni elementët në vende.
- Merrni dy elementët e parë si një sekuencë të renditur.
- Shko te artikulli i tretë.
- Krahasojeni me të dytin, ndërroni nëse është e nevojshme.
- Nëse është bërë zëvendësimi, krahasojeni me të parën.
- Merr tre elemente si një sekuencë të renditur.
E kështu me radhë deri në fund të grupit origjinal.
Rendimi i futjes në jetën reale
Për qartësi, ia vlen të jepet një shembull se si përdoret ky mekanizëm klasifikimi në jetën e përditshme.
Merrni, për shembull, një portofol. Kartëmonedhat njëqind, pesëqind dhe mijëra dollarësh qëndrojnë të çrregullta në ndarjen e kartëmonedhave. Kjo është një rrëmujë, në një rrëmujë të tillë është e vështirë të gjesh menjëherë copën e duhur të letrës. Vargu i kartëmonedhave duhet të renditet.
E para është një kartëmonedhë 1000 rubla, dhe menjëherë pas saj - 100. Marrim njëqind dhe e vendosim përpara. E treta me radhë është 500 rubla, vendi i duhur për të është midis njëqind dhe një mijë.
Në të njëjtën mënyrë ne i renditim letrat e marra kur luajmë "Budallai" për ta bërë më të lehtë lundrimin në to.
Operatorët dhe funksionet ndihmëse
Metoda e renditjes së futjes merr si hyrje një grup fillestar për t'u renditur, një funksion krahasimi dhe, nëse është e nevojshme, një funksion që përcakton rregullin për numërimin e elementeve. Më shpesh përdoret në vend të kësajdeklaratë e ciklit të rregullt.
Elementi i parë është në vetvete një grup i renditur, kështu që krahasimi fillon nga i dyti.
Algoritmi shpesh përdor një funksion ndihmës për të shkëmbyer dy vlera (ndërrim). Ai përdor një ndryshore shtesë të përkohshme, e cila konsumon kujtesën dhe ngadalëson pak kodin.
Një alternativë është zhvendosja në masë e një grupi elementësh dhe më pas futja e atij aktual në hapësirën e lirë. Në këtë rast, kalimi në elementin tjetër ndodh kur krahasimi dha një rezultat pozitiv, i cili tregon renditjen e saktë.
Shembuj zbatimi
Zbatimi specifik varet kryesisht nga gjuha e programimit e përdorur, sintaksa dhe strukturat e saj.
Zbatimi klasik C duke përdorur një variabël të përkohshëm për të shkëmbyer vlerat:
int i, j, temp; për (i=1; i =0; j--) { if (array[j] < temp) break; grup[j + 1]=grup[j]; grup[j]=temp; } }
Zbatimi PHP:
funksioni insertion_sort(&$a) {për ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Këtu, së pari, të gjithë elementët që nuk përputhen me kushtin e renditjes zhvendosen djathtas dhe më pas elementi aktual futet në hapësirën e lirë.
Kodi Java duke përdorur ciklin while:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Kuptimi i përgjithshëm i kodit mbetet i pandryshuar: çdo element i grupit krahasohet në mënyrë sekuenciale me ato të mëparshmet dhe zëvendësohet me to nëse është e nevojshme.
Koha e përllogaritur e funksionimit
Natyrisht, në rastin më të mirë, hyrja e algoritmit do të jetë një grup tashmë i renditur në mënyrën e duhur. Në këtë situatë, algoritmi thjesht do të duhet të kontrollojë çdo element për t'u siguruar që është në vendin e duhur pa bërë shkëmbime. Kështu, koha e ekzekutimit do të varet drejtpërdrejt nga gjatësia e grupit origjinal O(n).
Inputi në rastin më të keq është një grup i renditur në rend të kundërt. Kjo do të kërkojë një numër të madh permutacionesh, funksioni i kohës së funksionimit do të varet nga numri i elementeve në katror.
Numri i saktë i permutacioneve për një grup krejtësisht të parregulluar mund të llogaritet duke përdorur formulën:
n(n-1)/2
ku n është gjatësia e grupit origjinal. Kështu, do të duheshin 4950 permutacione për të renditur 100 elementë në rendin e duhur.
Metoda e futjes është shumë efikase për renditjen e grupeve të vogla ose pjesërisht të renditura. Megjithatë, nuk rekomandohet aplikimi i tij kudo për shkak të kompleksitetit të lartë të llogaritjeve.
Algoritmi përdoret si ndihmës në shumë metoda të tjera më komplekse të renditjes.
Rendit vlerat e barabarta
Algoritmi i futjes i përket të ashtuquajturave lloje të qëndrueshme. Do te thote,se nuk ndërron elemente identike, por ruan rendin e tyre origjinal. Indeksi i stabilitetit është në shumë raste i rëndësishëm për renditjen e saktë.
Sa më sipër është një shembull i mrekullueshëm vizual i llojit të futjes në një kërcim.
