streamalism.org

1. Introduktion

I denne vejledning forklarer vi, hvordan sorteringsalgoritmen på stedet fungerer.

2. Placeringsalgoritmer

Placeringsalgoritmerne er dem, der ikke har brug for hjælpedatastruktur for at transformere inputdataene. Dybest set betyder det, at algoritmen ikke bruger ekstra plads til inputmanipulation. Det tilsidesætter praktisk talt input med output.

Imidlertid kan algoritmen faktisk kræve en lille og ikke-konstant ekstra plads til hjælpevariabler. Kompleksiteten i dette rum er i de fleste tilfælde O (log n), selvom der undertiden er tilladt noget mindre end lineært.

3. Pseudokode

Lad os nu se noget pseudokode og sammenligne algoritmen på stedet med den sted, der ikke er på stedet.

Vi antager, at vi vil vende en række af n numre.

3.1. Placeringsalgoritme

Hvis vi tænker på problemet, ser vi, at vi har et input-array og en reverse array som output. I sidste ende har vi faktisk ikke brug for vores originale array, kun den omvendte.

Så hvorfor overskriver vi ikke input i stedet for at flytte dets værdier til det helt nye array, da det kan se ud som en mest åbenbar metode? At gøre det, vi behøver kun en ekstra variabel for midlertidigt at gemme de værdier, som vi i øjeblikket arbejder med:

reversInPlace (array A [n]) for i fra 0 til n / 2 temp = A [i] A [i] = A [n - 1 - i] A [n - 1 - i] = temp

Det er bemærkelsesværdigt at nævne, at uanset hvor stort arrayet er, vil den ekstra plads, vi har brug for, altid være O (1) I dette tilfælde.

Illustrationen viser, at vi har brug for færre trin end i det foregående tilfælde:

3.2. Ikke-sted algoritme

På den anden side kan vi også gøre dette på en ret enkel og mere indlysende måde. Vi kan oprette en ny matrix af samme størrelse, kopiere værdierne fra den oprindelige i den tilsvarende rækkefølge og derefter slette den originale matrix:

reverseOutOfPlace (array A [n]) opret ny array B [n] for i fra 0 til n - 1 B [i] = A [i] slet A return B

Selvom dette vil gøre, hvad vi ville have det, er det ikke effektivt nok. Vi har På) ekstra plads krævesda vi har to arrays at manipulere med. Derudover er oprettelse og fjernelse af et nyt array normalt en langsom handling.

Lad os se illustrationen af ​​processen:

4. Java-implementering

Lad os nu se, hvordan vi kan implementere i Java, hvad vi lærte i det foregående afsnit.

For det første implementerer vi en lokal algoritme:

offentlig statisk int [] reverseInPlace (int A []) {int n = A. længde; for (int i = 0; i <n / 2; i ++) {int temp = A [i]; A [i] = A [n - 1 - i]; A [n - 1 - i] = temp; } returnere A; }

Vi kan let teste, at dette fungerer som forventet:

@ Test offentligt ugyldigt givenArray_whenInPlaceSort_thenReversed () {int [] input = {1, 2, 3, 4, 5, 6, 7}; int [] forventet = {7, 6, 5, 4, 3, 2, 1}; assertArrayEquals ("de to arrays er ikke ens", forventes, InOutSort.reverseInPlace (input)); }

For det andet, lad os tjekke implementeringen af ​​algoritme, der ikke er i stedet:

offentlig statisk int [] reverseOutOfPlace (int A []) {int n = A. længde; int [] B = ny int [n]; for (int i = 0; i <n; i ++) {B [n - i - 1] = A [i]; } returnere B; }

Testen er ret ligetil:

@ Test offentligt ugyldigt givenArray_whenOutOfPlaceSort_thenReversed () {int [] input = {1, 2, 3, 4, 5, 6, 7}; int [] forventet = {7, 6, 5, 4, 3, 2, 1}; assertArrayEquals ("de to arrays er ikke ens", forventes, InOutSort.reverseOutOfPlace (input)); }

5. Eksempler

Der er mange sorteringsalgoritmer, der bruger in-place tilgang. Nogle af dem er indsættelsessortering, boblesortering, dyngesortering, quicksort og shell-sortering, og du kan lære mere om dem og tjekke deres Java-implementeringer.

Vi skal også nævne kamsortering og heapsort. Alle disse har pladskompleksitet O (log n).

Det kan også være nyttigt at lære mere om teorien om Big-O Notation samt at tjekke nogle praktiske Java-eksempler om algoritmens kompleksitet.

6. Konklusion

I denne artikel beskrev vi de såkaldte in-place algoritmer, illustrerede, hvordan de fungerer ved hjælp af pseudocode og et par eksempler, opregnede flere algoritmer, der fungerer på dette princip, og implementerede endelig de grundlæggende eksempler i Java.

Som sædvanlig kunne hele koden findes på GitHub.