Guide til stedlig sorteringsalgoritme Fungerer med en Java-implementering

1. Introduksjon

I denne opplæringen forklarer vi hvordan sorteringsalgoritmen på stedet fungerer.

2. Lokale algoritmer

In-place algoritmene er de som ikke trenger hjelpedatastruktur for å transformere inngangsdataene. I utgangspunktet betyr det at algoritmen ikke bruker ekstra plass til inngangsmanipulering. Det overstyrer praktisk talt inngangen med utgangen.

Imidlertid kan algoritmen faktisk kreve en liten og ikke-konstant ekstra plass for hjelpevariabler. Kompleksiteten til dette rommet er i de fleste tilfeller O (log n), selv om noen ganger er noe mindre enn lineært tillatt.

3. Pseudokode

La oss nå se litt pseudokode og sammenligne algoritmen på stedet med den utenfor stedet.

Vi antar at vi vil reversere en rekke n tall.

3.1. Lokal algoritme

Hvis vi tenker på problemet, ser vi at vi har en inngangsrute og omvendt matrise som utdata. Til slutt trenger vi faktisk ikke vår opprinnelige matrise, bare den omvendte.

Så hvorfor skulle vi ikke overskrive inndata i stedet for å flytte verdiene til den helt nye matrisen, da det kan se ut som en mest åpenbar metode? Å gjøre det, vi trenger bare en ekstra variabel for å lagre verdiene som vi jobber med midlertidig:

reversInPlace (matrise 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 bemerkelsesverdig å nevne at uansett hvor stor matrisen er, vil den ekstra plassen vi trenger alltid være O (1) i dette tilfellet.

Illustrasjonen viser at vi trenger færre trinn enn i forrige tilfelle:

3.2. Ikke-sted-algoritme

På den annen side kan vi også gjøre dette på en ganske enkel, mer åpenbar måte. Vi kan opprette en ny matrise av samme størrelse, kopiere verdiene fra den opprinnelige i tilsvarende rekkefølge og deretter slette den originale matrisen:

reverseOutOfPlace (matrise A [n]) opprett ny matrise B [n] for i fra 0 til n - 1 B [i] = A [i] slett A retur B

Selv om dette vil gjøre det vi ønsket det, er det ikke effektivt nok. Vi har På) ekstra plass krevessiden vi har to matriser å manipulere med. I tillegg til det er det langsomt å lage og fjerne en ny matrise.

La oss se illustrasjonen av prosessen:

4. Java-implementering

La oss nå se hvordan vi kan implementere i Java det vi lærte i forrige avsnitt.

For det første implementerer vi en på plass algoritme:

offentlig statisk int [] reverseInPlace (int A []) {int n = A.lengde; 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 enkelt teste at dette fungerer som forventet:

@Test offentlig ugyldig givenArray_whenInPlaceSort_thenReversed () {int [] input = {1, 2, 3, 4, 5, 6, 7}; int [] forventet = {7, 6, 5, 4, 3, 2, 1}; assertArrayEquals ("de to matriser er ikke like", forventet, InOutSort.reverseInPlace (input)); }

For det andre, la oss sjekke implementeringen av algoritme som ikke er på plass:

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

Testen er ganske grei:

@Test offentlig ugyldig givenArray_whenOutOfPlaceSort_thenReversed () {int [] input = {1, 2, 3, 4, 5, 6, 7}; int [] forventet = {7, 6, 5, 4, 3, 2, 1}; assertArrayEquals ("de to matriser er ikke like", forventet, InOutSort.reverseOutOfPlace (input)); }

5. Eksempler

Det er mange sorteringsalgoritmer som bruker tilnærming på stedet. Noen av dem er innsettingssortering, boblesortering, haugsortering, kviksortering og skallsortering, og du kan lære mer om dem og sjekke ut Java-implementeringene deres.

Vi må også nevne kamsortering og høysort. Alle disse har plasskompleksitet O (log n).

Det kan også være nyttig å lære mer om Theory of Big-O Notation, samt å sjekke ut noen praktiske Java-eksempler om kompleksiteten i algoritmen.

6. Konklusjon

I denne artikkelen beskrev vi de såkalte algoritmene på stedet, illustrerte hvordan de fungerer ved hjelp av pseudokode og noen få eksempler, listet opp flere algoritmer som fungerer etter dette prinsippet, og til slutt implementerte de grunnleggende eksemplene i Java.

Som vanlig kunne hele koden bli funnet på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found