Algoritam za sortiranje u mestu
U kompjuterskoj tehnologiji, algoritam za sortiranje u mestu je algoritam koji transformiše ulaz koristeći strukturu podataka sa malom,konstantnom količinom dodatnog prostora.Ulaz je najčešće zamenjen izlazom kako se algoritam izvršava.Algoritam koji ne sortira u mestu ponekad se zove izvan mesta ili ne u mestu.
Algoritam se ponekad, neformalno, zove u mestu dok god vrši zamenu ulaza izlazom.U stvarnosti, ovo nije dovoljno , niti je potrebno; izlazni prostor može biti konstantan, ili ne mora čak ni da se uzima u obzir, na primer ako se izlaz ispisuje na tok.Sa druge strane, ponekad može biti praktično da se uzme u obzir izlazni prostor kako bi se odredilo da li je algoritam u mestu, kao što je u prvom primeru ispod; ovo otežava da striktno definišemo algoritme u mestu.U teorijskoj primeni, kao što je smanjenje log prostora, tipično je da es uvek ignoriše izlazni prostor(u ovakvim slučajevima je od veće vaznosti da je izlaz samo za pisanje).
Primeri уреди
Dat je niz a do n elemenata, pretpostavimo da hoćemo niz koji sadrži iste elemente u obrnutom redosledu i da hoćemo da se oslobodimo prvobitnog niza.Jedan, kako se čini, jednostavan način da se ovo uradi je da se kreira novi niz jednake veličine, napuni kopijama elemenata prvobitnog niza u određenom redosledu, i da se izbriše prvobitni niz.
function reverse(a[0..n - 1])
allocate b[0..n - 1]
for i from 0 to n - 1
b[n − 1 − i] := a[i]
return b
Nažalost ovo zahteva O(n) dodatnog prostora kako bi smo imali nizove a i b dostupne istovremeno.Takođe alokacija i dealokacija su često spore operacije.Pošto nam vise ne treba niz a, možemo da ga zamenimo sa njegovim elementima, poređanim u suprotnom poredku, koristeći ovaj algoritam u mestu kome će samo trebati konstantan dodatni prostor za pomoćne promenljive i i tmp, bez obzira na veličinu niza.
function reverse_in_place(a[0..n])
for i from 0 to floor(n/2)
tmp := a[i]
a[i] := a[n − 1 − i]
a[n − 1 − i] := tmp
Postoji veliki broj algoritama za sortiranje, koji mogu da preurede niz u sortiranom redosledu, bez korišćenja dodatnog niza.U te algoritme spadaju: Mehur sortiranje,Češalj sortiranje,sortiranje Selekcijom,sortiranje Umetanjem, Hip sortiranje,Školjka sortiranje.
Brzo sortiranje sortira podatke u mestu , kako uvek vrši zamenu samo dva elementa niza.Međutim, većina implementacija zahteva O(log n) prostora kako bi vodilo evidenciju o rekurzivnim pozivima funkcije kao deo podeli i vladaj strategije; pa Brzo sortiranje nije algoritam koji sortira u mestu.
Većina algoritama koji sortiraju selekcijom su takođe u mestu, mada neki znatno preuređuju ulazni niz u procesu pronalaženja konačnog rezultata konstantne veličine.
Neki algoritmi za obradu teksta, kao sto su trim i reverse mogu biti urađeni u mestu.
уреди
U teoriji izračunavanja složenosti, algoritmi u mestu uključuju sve algoritme sa O(1) prostornom složenošću, klase DSPACE(1).Ova klasa je veoma ograničena; jednaka je regularnim jezicima.Zapravo, ne uključuje primere navedene iznad.
Zbog ovog razloga, uzimamo u obzir algoritme u L klasi, klasa problema koja zahteva O(log n) dodatnog prostora, da bi bili u mestu.Iako ovo izgleda suprotno našoj ranijoj definiciji, moramo uzeti u obzir da u apstraktnom sveu naš ulaz može biti proizvoljno velik.Na pravom računaru, pokazivač zahteva malu, fiksnu količinu prostora, jer je količina fizičke memorije ograničena, ali generalno O(log n) bitova je potrebno da se odredi indeks u listi veličine n.
Da li ovo znači da je brzo sortiranje algoritam koji radi u mestu? Nimalno – tehnički, zahteva O(log2 n) prostora, pošto svako od O(log n) stek okvira sadrži konstantan broj pokazivača(svako veličine O(log n)).
Određivanje algoritama u mestu, koji pripadaju klasi L, ima veoma zanimljive posledice; na primer, to znači da postoji algoritam u mestu(prilično složen) pomoću kojeg moze da se utvrdi da li postoji putanja između dva čvora u neusmerenom grafu, problem koji zahteva O(n) dodatnog prostora koristeći standardne algoritme kao sto je što je algoritam za pretragu grafa u dubinu.Ovo zauzvrat daje algoritme u mestu za probleme kao što su određivanje da li je graf bipartitivan ili testiranje da li dva grafa imaju isti broj komponenti.Pogledajte SL za više informacija.
Uloga nasumičnosti уреди
U dosta slučajeva, prostor potreban za algoritam može drastično biti smanjen korstići algoritam za randomizaciju.Na primer,recimo da hoćemo da znamo da li su dva temena u grafu, od n temena, u istoj povezanoj komponenti grafa.Nema jednostavnog, determinističkog, u mestu algoritma da se ovo odredi, ali ako počnemo od jednog temena i vršimo slučajnu šetnju od oko 20*n3 koraka, šansa da ćemo da naiđemo na temen, pod pretpostavkom da je u istoj komponenti, je veoma velika.Slično, postoje jednostavni algoritmi u mestu koji koriste randomizaciju za prosto tesitranje, kao što je Miller-Rabin prost test,a tu su I jednostavni algoritmi u mestu koji koriste nasumično faktorisanje, kao što je Pollard's rho algorithm.Pogledajte RL I BPL za diskusiju ovog fenomena.
U funkcionalnom programiranju уреди
Jezici funkcionalnog programiranja često obeshrabruju ili ne podržavaju algoritme u mesto koje prepisuju preko podataka, jer je ovo tip sporednog efekta; umesto toga, oni samo dozvoljavaju da se novi podaci izgrade.Međutim, dobri kompajleri funkcionalnih jezika često će prepoznati kada je objekat sličan postojećem kreiran I onda se stari odbacuje, I onda će optimizovati ovo u jednostavnu mutaciju “ispod-haube”.
Primetiti da je moguće ,u principu ,da se pažljivo konstruiše algoritam u mestu koje ne menja podatke(osim ako se podaci više ne koriste), ali ovo je retko rađeno u praksi.Pogledajte čisto funkcionalne strukture podataka.