streamalism.org

1. Áttekintés

Ebben az oktatóanyagban megvitatjuk a Insertion Sort algoritmust, és nézze meg annak Java megvalósítását.

Az Insertion Sort egy hatékony algoritmus kis számú elem megrendelésére. Ez a módszer azon alapszik, hogy a kártyajátékosok hogyan válogatják össze a kezüket.

Üres bal kézzel és az asztalra letett kártyákkal kezdjük. Ezután egy-egy kártyát kiveszünk az asztalról, és a bal kézbe helyezzük a megfelelő helyzetbe. Az új kártya helyes helyzetének megtalálásához összehasonlítjuk a kezében már rendezett kártyakészlettel, jobbról balra.

Kezdjük azzal, hogy megértjük az algoritmus lépéseit álkód formában.

2. Álkód

Bemutatjuk az álkódunkat a beillesztés rendezésére, úgynevezett eljárásként BETÖLTÉS-VÁLASZTÁS, paraméterként egy tömböt vesz A [1 .. n] n rendezni kívánt elem közül. Az algoritmus a bemeneti tömböt a helyén rendezi (az A tömb elemeinek átrendezésével).

Az eljárás befejezése után az A bemeneti tömb tartalmazza a bemeneti szekvencia permutációját, de sorrendben:

INSERTION-SORT (A) i = 2-től A.-ig. Hosszúságkulcs = A [i] j = i - 1, míg j> 0 és A [j]> A [j + 1] = A [j] j = j - 1 A [j + 1] = kulcs

Nézzük át röviden a fenti algoritmust.

Az index én jelzi az aktuális elem pozícióját a feldolgozandó tömbben.

A második elemből indulunk ki, mivel definíció szerint egy tételből álló tömb rendezettnek tekinthető. Az elem az indexen én nevezzük a kulcs. Miután az kulcs, az algoritmus második része a helyes indexének megtalálásával foglalkozik. Ha a kulcs kisebb, mint az elem értéke az indexen j, akkor a gomb egy pozícióval balra mozog. A folyamat addig folytatódik, amíg el nem érünk egy elemet, amely kisebb, mint a kulcs.

Fontos megjegyezni, hogy az iteráció megkezdése előtt meg kell találni a kulcs indexnél én, a tömb A [1 .. j - 1] már van válogatott.

3. A kötelező végrehajtás

A kényszeres esetre írunk egy nevű függvényt insertionSortImperative, paraméterként egy egész szám tömböt vesz fel. A függvény a második elem tömbjén kezd iterálni.

Az iteráció során bármikor, úgy gondolhatnánk, hogy ez a tömb logikusan két részre oszlik; a bal oldal a rendezett és a jobb oldal a még nem rendezett elemeket tartalmazza.

Fontos megjegyzés, hogy miután megtaláltuk a megfelelő helyet, ahová beillesztjük az új elemet, az elemeket jobbra toljuk (és nem cseréljük) hogy helyet szabadítson fel neki.

public static void insertionSortImperative (int [] input) {for (int i = 1; i = 0 && input [j]> kulcs) {input [j + 1] = input [j]; j = j - 1; } input [j + 1] = kulcs; }}

Ezután hozzunk létre egy tesztet a fenti módszerhez:

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

A fenti teszt bizonyítja, hogy az algoritmus rendezi a bemeneti tömb növekvő sorrendjét .

4. Rekurzív megvalósítás

Meghívjuk a rekurzív eset függvényét insertionSortRecurzív és befogad egész szám tömböt (ugyanaz, mint a kötelező eseteknél).

A kényszeres esetektől (annak ellenére, hogy rekurzív) itt a különbség az túlterhelt függvényt hív meg egy második argumentummal, amely megegyezik a rendezni kívánt elemek számával.

Mivel a teljes tömböt rendezni akarjuk, a hosszával megegyező számú elemet adunk át:

public static void insertionSortRecursive (int [] input) {insertionSortRecursive (input, input.length); }

A rekurzív eset egy kicsit nagyobb kihívást jelent. Az alapeset akkor fordul elő, amikor egy tömböt megpróbálunk egy elemmel rendezni. Ebben az esetben nem teszünk semmit.

Az összes ezt követő rekurzív hívás a bemeneti tömb előre meghatározott részét rendezi - a második tételtől kezdve a tömb végéig:

private static void insertionSortRecursive (int [] input, int i) {if (i <= 1) {return; } insertionSortRecursive (input, i - 1); int kulcs = bemenet [i - 1]; int j = i - 2; while (j> = 0 && input [j]> gomb) {input [j + 1] = input [j]; j = j - 1; } input [j + 1] = kulcs; }

És így néz ki a hívásverem egy 6 elemből álló bemeneti tömbnél:

insertionSortRecursive (input, 6) insertionSortRecursive (input, 5) és helyezze be a 6. elemet a rendezett tömbbe insertionSortRecursive (input, 4), és helyezze be az 5. elemet a rendezett tömbbe insertionSortRecursive (input, 3), és illessze be a 4. elemet a rendezett array insertionSortRecursive (input, 2), és illessze be a 3. elemet a rendezett tömb insertionSortRecursive (input, 1) elembe, és illessze be a 2. elemet a rendezett tömbbe

Lássuk a tesztet is:

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

A fenti teszt bizonyítja, hogy az algoritmus rendezi a bemeneti tömb növekvő sorrendjét .

5. Idő és tér komplexitás

Az az idő, amelyet a BETÖLTÉS-VÁLASZTÁS eljárás futtatásához O (n ^ 2). Minden új elemnél jobbról balra iterálunk a tömb már rendezett része fölött, hogy megtaláljuk a helyes helyzetét. Ezután úgy helyezzük be, hogy az elemeket egy pozícióval jobbra toljuk.

Az algoritmus a helyén rendeződik, így az a tér bonyolultsága az O (1) a kötelező végrehajtásért és Tovább) a rekurzív megvalósításhoz.

6. Következtetés

Ebben az oktatóanyagban láttuk, hogyan lehet megvalósítani a beillesztés rendezését.

Ez az algoritmus hasznos kis számú elem rendezéséhez. 100-nál több elemet tartalmazó bemeneti szekvencia válogatásakor hatástalanná válik.

Ne feledje, hogy másodfokú bonyolultsága ellenére a helyére rendeződik, anélkül, hogy kisegítő hely kellene, mint például egyesítés rendezés.

A teljes kód megtalálható a GitHubon.