streamalism.org

1. Uvod

U ovom uputstvu objasnit ćemo kako funkcionira algoritam sortiranja na mjestu.

2. Algoritmi na mjestu

Ugrađeni algoritmi su oni kojima nije potrebna pomoćna struktura podataka kako bi transformirali ulazne podatke. U osnovi, to znači da algoritam ne koristi dodatni prostor za manipulaciju ulazom. Praktički nadjačava ulaz i izlaz.

Međutim, u stvarnosti algoritam zapravo može zahtijevati mali i nestalni dodatni prostor za pomoćne varijable. Složenost ovog prostora je u većini slučajeva O (zapisnik n), iako je ponekad dopušteno i nešto manje od linearnog.

3. Pseudokod

Pogledajmo sada pseudokod i usporedimo algoritam na mjestu s onim koji nije na mjestu.

Pretpostavit ćemo da želimo preokrenuti niz od n brojevi.

3.1. Algoritam na mjestu

Ako razmislimo o problemu, vidjet ćemo da imamo izlazni niz i obrnuti niz kao izlaz. Na kraju, zapravo nam ne treba naš izvorni niz, već samo obrnuti.

Zašto onda ne bismo prepisali ulaz umjesto da njegove vrijednosti premjestimo u potpuno novi niz, jer to može izgledati kao najočitija metoda? Napraviti to, trebat će nam samo jedna dodatna varijabla za privremeno spremanje vrijednosti s kojima trenutno radimo:

reversInPlace (niz A [n]) za i od 0 do n / 2 temp = A [i] A [i] = A [n - 1 - i] A [n - 1 - i] = temp

Vrijedno je spomenuti da, bez obzira koliko velik niz bio, dodatni prostor koji nam treba uvijek će biti O (1) u ovom slučaju.

Ilustracija pokazuje da nam treba manje koraka nego u prethodnom slučaju:

3.2. Algoritam izvan mjesta

S druge strane, to također možemo učiniti na prilično jednostavan, očitiji način. Možemo stvoriti novi niz iste veličine, kopirati vrijednosti iz izvornog u odgovarajućem redoslijedu, a zatim izbrisati izvorni niz:

reverseOutOfPlace (niz A [n]) stvori novi niz B [n] za i od 0 do n - 1 B [i] = A [i] izbriši A povratak B

Iako će ovo učiniti ono što smo htjeli, nije dovoljno učinkovito. Imamo Na) potreban dodatni prostorbudući da imamo dva niza za manipulaciju. Osim toga, stvaranje i uklanjanje novog niza obično je spora operacija.

Pogledajmo ilustraciju postupka:

4. Implementacija Jave

Pogledajmo sada kako u Java možemo implementirati ono što smo naučili u prethodnom odjeljku.

Prvo, implementirat ćemo algoritam na mjestu:

javni statički int [] reverseInPlace (int A []) {int n = A.dužina; za (int i = 0; i <n / 2; i ++) {int temp = A [i]; A [i] = A [n - 1 - i]; A [n - 1 - i] = temp; } povratak A; }

Možemo lako testirati da li ovo funkcionira prema očekivanjima:

@Test javna praznina givenArray_whenInPlaceSort_thenReversed () {int [] input = {1, 2, 3, 4, 5, 6, 7}; int [] očekuje se = {7, 6, 5, 4, 3, 2, 1}; assertArrayEquals ("dva polja nisu jednaka", očekuje se, InOutSort.reverseInPlace (ulaz)); }

Drugo, provjerimo implementaciju algoritma koji nije mjesto:

javni statički int [] reverseOutOfPlace (int A []) {int n = A.dužina; int [] B = novo int [n]; za (int i = 0; i <n; i ++) {B [n - i - 1] = A [i]; } povratak B; }

Test je prilično jednostavan:

@Test javna praznina givenArray_whenOutOfPlaceSort_thenReversed () {int [] input = {1, 2, 3, 4, 5, 6, 7}; int [] očekuje se = {7, 6, 5, 4, 3, 2, 1}; assertArrayEquals ("dva polja nisu jednaka", očekuje se, InOutSort.reverseOutOfPlace (ulaz)); }

5. Primjeri

Postoji mnogo algoritama za sortiranje koji koriste pristup na mjestu. Neki od njih su sortiranje umetanjem, mjehurići, sortiranje hrpe, brzo sortiranje i sortiranje ljuske, a možete saznati više o njima i provjeriti njihove Java implementacije.

Također, moramo spomenuti sortu češlja i sortu češlja. Sve ovo ima složenost prostora O (zapisnik n).

Također bi moglo biti korisno naučiti više o teoriji Big-O notacije, kao i provjeriti neke praktične Java primjere o složenosti algoritma.

6. Zaključak

U ovom smo članku opisali takozvane in-place algoritme, ilustrirali kako oni rade pomoću pseudo koda i nekoliko primjera, naveli nekoliko algoritama koji rade na ovom principu i na kraju implementirali osnovne primjere u Javi.

Kao i obično, cijeli se kôd može naći na GitHubu.