streamalism.org

1. Bemutatkozás

Ebben az oktatóanyagban elmagyarázzuk, hogyan működik a hely szerinti rendezési algoritmus.

2. Helyi algoritmusok

A helyi algoritmusok azok, amelyeknek nincs szükségük kiegészítő adatokra a bemenő adatok átalakításához. Alapvetően ez azt jelenti, hogy az algoritmus nem használ extra helyet a bemeneti manipulációhoz. Gyakorlatilag felülírja a bemenetet a kimenettel.

Azonban a valóságban az algoritmus valójában kis és nem állandó kiegészítő helyet igényelhet a segédváltozók számára. Ennek a térnek a bonyolultsága a legtöbb esetben O (log n), bár néha bármi megengedett, mint a lineáris.

3. Álkód

Lássunk most egy álkódot, és hasonlítsuk össze a helyben lévő algoritmust a nem megfelelő algoritmussal.

Feltételezzük, hogy meg akarunk fordítani egy tömböt n számok.

3.1. Helyi algoritmus

Ha belegondolunk a problémába, látni fogjuk, hogy kimenetként bemeneti tömb és fordított tömb van. Végül valójában nincs szükségünk eredeti tömbünkre, csak a fordítottra.

Akkor miért ne írnánk felül az inputot, ahelyett, hogy az értékeit a teljesen új tömbbe helyeznénk, mivel ez a legkézenfekvőbb módszernek tűnhet? Ehhez, csak egy további változóra lesz szükségünk ideiglenesen tárolja azokat az értékeket, amelyekkel jelenleg dolgozunk:

reversInPlace (A [n] tömb) i-re 0-tól n / 2-ig temp = A [i] A [i] = A [n - 1 - i] A [n - 1 - i] = hőmérséklet

Figyelemre méltó megemlíteni, hogy bármekkora is a tömb, a szükségünkre álló extra hely mindig lesz O (1) ebben az esetben.

Az ábra azt mutatja, hogy kevesebb lépésre van szükségünk, mint az előző esetben:

3.2. Helyen kívüli algoritmus

Másrészt ezt elég egyszerű, kézenfekvőbb módon is megtehetjük. Létrehozhatunk egy ugyanolyan méretű tömböt, átmásolhatjuk az értékeket az eredetiről a megfelelő sorrendben, majd törölhetjük az eredeti tömböt:

A reverseOutOfPlace (A [n] tömb) új B [n] tömböt hoz létre i-re 0-tól n-ig - 1 B [i] = A [i] töröl egy A visszatérést B

Bár ez megteszi azt, amit szerettünk volna, nem elég hatékony. Nekünk van Tovább) extra hely szükségesmivel két tömböt kell kezelnünk. Emellett az új tömb létrehozása és eltávolítása általában lassú művelet.

Lássuk a folyamat szemléltetését:

4. Java implementáció

Most nézzük meg, hogyan tudjuk megvalósítani a Java-ban az előző szakaszban tanultakat.

Először megvalósítunk egy helyben működő algoritmust:

public static int [] reverseInPlace (int A []) {int n = A.hossz; for (int i = 0; i <n / 2; i ++) {int temp = A [i]; A [i] = A [n - 1 - i]; A [n - 1 - i] = hőmérséklet; } return A; }

Könnyen tesztelhetjük, hogy ez a várt módon működik-e:

@Test public void givenArray_whenInPlaceSort_thenReversed () {int [] input = {1, 2, 3, 4, 5, 6, 7}; int [] várható = {7, 6, 5, 4, 3, 2, 1}; assertArrayEquals ("a két tömb nem egyenlő", várható, InOutSort.reverseInPlace (input)); }

Másodszor, nézzük meg az out-of-place algoritmus megvalósítását:

public static int [] reverseOutOfPlace (int A []) {int n = A.hossz; int [] B = új int [n]; mert (int i = 0; i <n; i ++) {B [n - i - 1] = A [i]; } visszatérés B; }

A teszt elég egyszerű:

@Test public void givenArray_whenOutOfPlaceSort_thenReversed () {int [] input = {1, 2, 3, 4, 5, 6, 7}; int [] várható = {7, 6, 5, 4, 3, 2, 1}; assertArrayEquals ("a két tömb nem egyenlő", várható, InOutSort.reverseOutOfPlace (input)); }

5. Példák

Számos rendezési algoritmus létezik, amelyek helyben történő megközelítést alkalmaznak. Némelyikük beillesztéses, buborékos, halom, sorrend és héj rendezés, és többet megtudhat róluk, és megnézheti a Java implementációikat.

Emellett meg kell említenünk a comb sort és a heapsort rendszert. Mindezek térbonyolultak O (log n).

Hasznos lehet többet megtudni a Big-O jelölés elméletéről, valamint megnézni néhány gyakorlati Java példát az algoritmus bonyolultságáról.

6. Következtetés

Ebben a cikkben ismertettük az úgynevezett helybeli algoritmusokat, bemutattuk, hogyan működnek pszeudokód és néhány példa felhasználásával, felsoroltunk számos algoritmust, amelyek ezen az elven működnek, és végül megvalósítottuk az alapvető példákat Java-ban.

Szokás szerint a teljes kód megtalálható a GitHubon.