Back

ⓘ Algoritam za sortiranje u mestu




                                     

ⓘ 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 prostoru ovakvim slučajevima je od veće vaznosti da je izlaz samo za pisanje.

                                     

1. 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 odredenom redosledu, i da se izbriše prvobitni niz.

function reverse 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 takode u mestu, mada neki znatno preureduju 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 uradeni u mestu.

                                     

2. Izračunavanje složenosti

U teoriji izračunavanja složenosti, algoritmi u mestu uključuju sve algoritme sa O1 prostornom složenošću, klase DSPACE1.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 Olog 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 Olog 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 Olog2 n prostora, pošto svako od Olog n stek okvira sadrži konstantan broj pokazivačasvako veličine Olog n).

Odredivanje algoritama u mestu, koji pripadaju klasi L, ima veoma zanimljive posledice; na primer, to znači da postoji algoritam u mestuprilično složen pomoću kojeg moze da se utvrdi da li postoji putanja izmedu dva čvora u neusmerenom grafu, problem koji zahteva On 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 odredivanje da li je graf bipartitivan ili testiranje da li dva grafa imaju isti broj komponenti.Pogledajte SL za više informacija.

                                     

3. 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 naidemo 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 Pollards rho algorithm.Pogledajte RL I BPL za diskusiju ovog fenomena.

                                     

4. 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.Medutim, 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 podatkeosim ako se podaci više ne koriste, ali ovo je retko radeno u praksi.Pogledajte čisto funkcionalne strukture podataka.