3. fejezet: Rendezési algoritmusok

A rendezés olyan folyamat, amely egy adatsorozat elemeinek átrendezésével logikus sorrendet hoz létre. Például a hitelkártya-számlád a tranzakciókat dátum szerint rendezi, és a könyveidet a szerzők és címek betűrendjében helyezed el a könyvespolcodon. A rendezés alapvető művelet a számítástudományban, és kritikus szerepet játszik számos alkalmazásban. Különböző klasszikus rendezési algoritmusok testesítik meg a probléma megoldásának különböző megközelítéseit.

Ebben a fejezetben több klasszikus rendezési módszert és egy fontos adatszerkezetet, a prioritási sort tárgyaljuk. Először néhány elemi rendezési módszerről, köztük a kiválasztásos rendezésről, a beszúrásos rendezésről és a Shellsort-ról beszélünk. Ezek a módszerek sok alkalmazásban megfelelőek, de nagy problémák esetén a rekurzív rendezési algoritmusokhoz, a egyesítéses rendezéshez és a gyorsrendezéshez fordulunk, amelyek segítségével hatalmas mennyiségű elemet lehet rendezni. Végül a prioritási sorokról és azok rendezésben és más alkalmazásokban való felhasználásáról beszélünk.

Elemi rendezések

A legegyszerűbb rendezési algoritmusok a következő műveleteket végzik:

Kiválasztásos rendezés: Megkeressük a legkisebb elemet, és kicseréljük az első bejegyzéssel, majd megkeressük a második legkisebb elemet, és kicseréljük a második bejegyzéssel, és így tovább.
Beszúrásos rendezés: Sorra vesszük az elemeket, és beillesztjük őket a már rendezett részbe a megfelelő helyre.

Ezek a műveletek tükrözik, ahogyan az emberek általában végzik a rendezési feladatokat, és kis problémaméret esetén hatékonyak. Azonban nem skálázódnak jól, és nagy tömbök rendezése esetén nem gyakorlati megoldások.

Kiválasztásos rendezés

A kiválasztásos rendezés egy egyszerű rendezési algoritmus, amely a következőképpen működik: Először megkeressük a legkisebb elemet a tömbben, és kicseréljük az első bejegyzéssel (ha az első bejegyzés már a legkisebb, akkor önmagával cseréljük ki). Ezután megkeressük a következő legkisebb elemet, és kicseréljük a második bejegyzéssel. Ezt a folyamatot folytatjuk, amíg a teljes tömb rendezett nem lesz.

A kiválasztásos rendezés belső ciklusaHere is the Hungarian translation of the provided markdown file, with the code comments translated:

A rendezés használata a a[i..N-1] rendezetlen részhalmazban található minimális elem megkereséséhez. A minimális elem indexe min-ben van tárolva. Ezután a[i] eleme kicserélésre kerül a[min]-nel, ami a minimális elemet a végleges helyére teszi. Ahogy az i index balról jobbra halad, a baloldalon lévő elemek már rendezettek a tömbben, és nem lesznek újra érintve.

Itt egy példa a szelekciós rendezés Java-ban való implementációjára:

public static void selectionSort(Comparable[] a) {
    // A tömb hossza
    int N = a.length;
    // Végigmegyünk a tömbön
    for (int i = 0; i < N; i++) {
        // A minimális elem indexe
        int min = i;
        // Megkeressük a minimális elemet a rendezetlen részhalmazban
        for (int j = i+1; j < N; j++) {
            if (less(a[j], a[min])) min = j;
        }
        // Kicseréljük a minimális elemet a jelenlegi elemmel
        exch(a, i, min);
    }
}

A szelekciós rendezés körülbelül ~N^2/2 összehasonlítást és N cserét használ egy N hosszúságú tömb rendezéséhez. A futási idő nem érzékeny a bemenetre - körülbelül ugyanannyi ideig tart a szelekciós rendezés egy már rendezett tömbön vagy egy egyenlő kulcsokkal rendelkező tömbön, mint egy véletlenszerűen rendezett tömbön.

Beszúrásos rendezés

A beszúrásos rendezés egy másik egyszerű rendezési algoritmus, amely a végső rendezett tömböt egy elemet építi fel egyszerre. Sokkal kevésbé hatékony nagy tömbökön, mint a fejlettebb algoritmusok, mint a gyorsrendezés, a kupacrendezés vagy az egyesítéses rendezés, de néhány előnye van:

Hatékony kis adathalmazok esetén.
Gyakorlatban hatékonyabb, mint a szelekciós rendezés.
Stabil; azaz nem változtatja meg az egyenlő kulcsokkal rendelkező elemek relatív sorrendjét.
In-place; azaz csak konstans O(1) további memóriahelyet igényel.
Online; azaz képes rendezni a listát, ahogy azt megkapja.

Itt egy példa a beszúrásos rendezés Java-ban való implementációjára:

public static void insertionSort(Comparable[] a) {
    // A tömb hossza
    int N = a.length;
    // Végigmegyünk a tömbön a második elemtől kezdve
    for (int i = 1; i < N; i++) {
        // Beszúrjuk a jelenlegi elemet a megfelelő helyre
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            // Kicseréljük a jelenlegi elemet az előtte lévővel
            exch(a, j, j-1);
        }
    }
}

A beszúrásos rendezés belső ciklusa a nagyobb elemeket egy pozícióval jobbra mozgatja, helyet csinálva a jelenlegi elem beszúrásához.Here is the Hungarian translation of the provided markdown file, with the code comments translated:

A beszúró rendezés futási ideje a bemeneti elemek kezdeti sorrendjétől függ. Például, ha a tömb nagy és a bejegyzések már rendezettek (vagy majdnem rendezettek), akkor a beszúró rendezés sokkal, sokkal gyorsabb, mint ha a bejegyzések véletlenszerűen vagy fordított sorrendben vannak.

Shellsort

A Shellsort a beszúró rendezés egyszerű kiterjesztése, amely a sebesség növelését azzal éri el, hogy lehetővé teszi a tömbben távol lévő bejegyzések cseréjét, hogy részlegesen rendezett tömbeket hozzon létre, amelyeket végül beszúró rendezéssel lehet hatékonyan rendezni.

Az ötlet az, hogy átrendezzük a tömböt, hogy az a tulajdonság legyen, hogy minden h-adik bejegyzés (bárhol is kezdve) egy rendezett részsorozatot ad. Ezt a tömböt h-rendezettnek nevezik. Más szóval, egy h-rendezett tömb h független rendezett részsorozat, amelyek egymásba vannak ágyazva. Néhány nagy h értékkel való h-rendezéssel a tömb elemeit nagy távolságokra mozgathatjuk, és így könnyebbé tehetjük a kisebb h értékekkel való h-rendezést. Ilyen eljárás alkalmazása bármely olyan értéksorozatra, amely 1-gyel végződik, rendezett tömböt fog eredményezni: ez a Shellsort.

Itt egy Shellsort implementáció Javában:

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N;
    
    public MaxPQ(int capacity) {
        pq = (Key[]) new Comparable[capacity+1];
    }
   
    public boolean isEmpty() {
        return N == 0;
    }
   
    public void insert(Key key) {
        pq[++N] = key;
        swim(N);
    }
   
    public Key delMax() {
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        pq[N+1] = null;
        return max;
    }
   
    private void swim(int k) {
        // Felúsztatás a csúcsig
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }
   
    private void sink(int k) {
        // Lesüllyesztés a csúcsig
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
   
    private booleaItt a magyar fordítás a megadott markdown fájlhoz. A kódban csak a kommenteket fordítottam le, a kód maga változatlan maradt.
 
```java
private boolean less(int i, int j) {
    // Visszaadja, hogy a i-edik elem kisebb-e, mint a j-edik elem
    return pq[i].compareTo(pq[j]) < 0;
}
 
private void exch(int i, int j) {
    // Kicseréli az i-edik és a j-edik elemet
    Key t = pq[i];
    pq[i] = pq[j];
    pq[j] = t;
}
}

Ez a kód egy maximális bináris kupac implementációját valósítja meg egy pq nevű tömb használatával. A beszúrás (insert()) és a maximum törlése (delMax()) műveletek a swim() és sink() segédmetódusok használatával tartják fenn a kupac tulajdonságot, azáltal, hogy kicserélik a kulcsokat, ha a szülő nagyobb, mint a gyermek, vagy a gyermek nagyobb, mint a szülő.

Stopwatch

Egy hasznosabb absztrakt adattípus egy egyszerű és hatékony stopperóra absztrakció, amely a szemközti oldalon látható. Használatához hozzon létre egy Stopwatch objektumot, amikor el akarja indítani a stopperórát, majd használja az elapsedTime() metódust a eltelt idő másodpercben való lekérdezéséhez a létrehozás óta. Az implementáció a Java System.currentTimeMillis() metódusát használja az aktuális idő milliszekundumban való lekérdezéséhez 1970. január 1. éjfél óta.

A start instance változó rögzíti a stopperóra létrehozásának idejét, és az elapsedTime() ezt használja fel az eltelt idő kiszámításához. A bemutatott ügyfél kód tipikus: végrehajt egy számítást, és egy Stopwatch segítségével méri, mennyi ideig tart a számítás. A Stopwatch adattípus hatékony absztrakció, mert elválasztja a stopperóra fogalmát (a felületet) a megvalósítástól (a Java System.currentTimeMillis() használatával). Ez a felület és megvalósítás szétválasztása az absztrakt adattípusok alapvető jellemzője, amelyet a könyv minden ADT-jében látni fogunk.

Összefoglalás

Az absztrakt adattípusok az objektum-orientált programozás lényeges elemei, amelyeket széles körben használnak a modern programozásban. Ebben a részben a következőket láttuk:

Absztrakt adattípus definiálása Java osztályként, instance változókkal az adattípus értékeinek meghatározására és instance metódusokkal az ezeken végzett műveletek megvalósítására.
Ugyanazon API többféle implementációjának kifejlesztése, különböző reprezentációkat használva ugyanahhoz az absztrakt adattípushoz.Absztrakt adattípus.
Az API-k, ügyfelek és implementációk megkülönböztetése egy absztrakt adattípuson belül.
Absztrakt adattípusok API-jának tervezése.
Ügyfelek és tesztügyfelek fejlesztése tesztelés és hibakeresés céljából.
Következtetés egy absztrakt adattípus implementációjának helyességéről, állítások használatával.
Különböző implementációk teljesítményének összehasonlítása ugyanazon API esetén.

Ezek a tevékenységek elengedhetetlen részei bármely Java-program fejlesztésének. Minden Java-program, amit írunk, könyvtárakból származó absztrakt adattípusok használatát fogja magában foglalni; sok közülük új absztrakt adattípusok fejlesztését is magában foglalja. A következő részben három alapvető absztrakt adattípust tárgyalunk, amelyek lényeges összetevői a programok nagy számának, és az 1.4. részben részletesen megvizsgáljuk az implementációk teljesítményjellemzőinek elemzésének folyamatát.

Chapter 2 Algorithms Fundamentals Chapter 4 Searching Algorithms