insertion sort

insertion sort (megszámlálható és megszámlálhatatlan, tsz. insertion sorts)

1. (informatika) beszúrásos rendezés

Az insertion sort (beszúró rendezés) egy egyszerű, de hatékony rendezési algoritmus kis és félig rendezett tömbök esetén. Működése során fokozatosan bővíti a már rendezett részhalmazt azzal, hogy a vizsgált elemet a megfelelő helyre szúrja be. Bár időkomplexitása négyzetes (O(n²)), a gyakorlati futása kis n értékeknél versenyképes lehet, ráadásul könnyen megérthető és megvalósítható C++ nyelven.

1. Kezdeti állapot: Tegyük fel, hogy adott egy rendezendő a tömb, melynek elemei a–tól a-ig terjednek. A nulladik elem (a) önmagában rendezettnek tekinthető.
2. Beillesztéses lépés: Iteráljunk végig a tömbön i=1–től i=n-1–ig. Minden lépésben a key = a értéket „felvesszük” és beszúrjuk a már rendezett részhalmazba (a), úgy hogy végigbalra tolunk minden nagyobb elemet, majd a key-t a szabaddá vált helyre helyezzük.
3. Rendezett rész frissítése: Így minden iteráció után a 0..i indexek közötti szegmens rendezetté válik. A végén – amikor i=n-1 is beillesztésre került – az egész tömb rendezett.

InsertionSort(a, n):
    for i = 1 to n-1:
        key = a
        j = i - 1
        while j ≥ 0 and a > key:
            a = a
            j = j - 1
        a = key

#include <iostream>
#include <vector>

// Beszúró rendezés függvénye
void insertionSort(std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    for (int i = 1; i < n; ++i) {
        int key = a;
        int j = i - 1;
        // Toljuk jobbra a nagyobb elemeket
        while (j >= 0 && a > key) {
            a = a;
            --j;
        }
        // Beszúrás a megfelelő helyre
        a = key;
    }
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6};
    std::cout << "Eredeti tömb: ";
    for (int x : arr) std::cout << x << ' ';
    std::cout << std::endl;

    insertionSort(arr);

    std::cout << "Rendezett tömb: ";
    for (int x : arr) std::cout << x << ' ';
    std::cout << std::endl;
    return 0;
}

Magyarázat

• A std::vector<int>& a referenciaként kapott tömböt módosítjuk helyben.
• A külső for-ciklus az aktuális „beszúrandó” elem indexét (i) futja végig.
• A belső while-ciklus a rendezett tartomány elemeit tolja jobbra addig, amíg nem talál kisebb vagy egyenlő értéket a key-re.
• A key beillesztése után a tömb elemei az 0..i tartományban rendezetté válnak.

• Stabilitás: Az insertion sort stabil rendezés, vagyis megegyező kulcsú elemek relatív sorrendje nem változik meg. Ez olyan alkalmazásokban fontos, ahol további szempontok is számítanak azonos értékek esetében.
• Helyigény: Eredeti adatok fölött, O(1) extra helyet használ, hiszen csak néhány segédváltozó (például key, i, j) szükséges.

• Átlag- és legrosszabb eseti: O(n²) idő, mivel minden elem beszúrása során a belső ciklus akár i-szor is lefuthat, így összesen ${\textstyle \sum _{i=1}^{n-1}i={\frac {n(n-1)}{2}}}$.
• Legjobb eseti: O(n), ha a tömb már rendezett (a belső while-ciklus sosem fut).
• Optimális használat: Kis tömbök (például n ≤ 20), vagy már részben rendezett tömbök esetén gyakran gyorsabb lehet, mint a komplexabb O(n log n) algoritmusok, amelyek belépési költsége magasabb.

Az egyszerű while-ciklus helyett a beszúrási pozíciót bináris kereséssel is meghatározhatjuk, így az összehasonlítások száma csökkenthető O(log n)-re, miközben az elemek eltolásának száma továbbra is O(n) marad:

#include <algorithm> // std::upper_bound

void insertionSortBinary(std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    for (int i = 1; i < n; ++i) {
        int key = a;
        // Megkeressük a beszúrás helyét bináris kereséssel
        int insertPos = std::upper_bound(a.begin(), a.begin() + i, key) - a.begin();
        // Előre másoljuk a beszúrandó elemet
        for (int j = i; j > insertPos; --j) {
            a = a;
        }
        a = key;
    }
}

Tegyük fel, hogy az a = . A rendezés folyamata:

1. i=1 (key=4): rendezett rész . 8 > 4 ⇒ tolás → , majd beszúrás → .
2. i=2 (key=5): rendezett rész . 8 > 5 ⇒ tolás → . 4 < 5 ⇒ megállunk, beszúrunk a j+1=1 pozícióba → .
3. i=3 (key=3): rendezett rész . 8 > 3 → ; 5 > 3 → ; 4 > 3 → ; j = -1 → beszúrás index 0 → . Végül rendezett tömb: .

Látható, hogy bár nagy adatmennyiségre a *Quick Sort*, *Merge Sort* és *Heap Sort* hatékonyabbak, az insertion sort előnye a stabilitás és a nagyon kis tömbökön, illetve részben rendezett adatokon felülmúlhatatlan egyszerűsége és alacsony állandó tényezője.

• Kis tömbök: Általában n ≤ 20–30 méretig versenyképes.
• Részben rendezett adatok: Ha az adatok majdnem sorbarendezettek, a futásideje közel lineárissá válik.
• Beágyazott rendszerek: Alacsony memóriakövetelmény és egyszerű kód miatt.
• Stabilitás: Ha fontos, hogy az egyenlő kulcsú elemek sorrendje megmaradjon.

Az insertion sort – bár időkomplexitása O(n²) – könnyen megérthető, stabil és helytakarékos rendező algoritmus. C++-ban néhány soros implementációval gyorsan használatba vehető, és kis vagy részben rendezetten levő adatok esetén akár jobb is lehet a bonyolultabb O(n log n) algoritmusoknál. Ha a rendezendő tömb mérete nagy, akkor érdemes gyorsabb algoritmusokat alkalmazni, de az insertion sort továbbra is alapvető eszköze a programozási ismereteknek és a valós alkalmazásoknak egyaránt.

• insertion sort - Szótár.net (en-hu)
• insertion sort - Sztaki (en-hu)
• insertion sort - Merriam–Webster
• insertion sort - Cambridge
• insertion sort - WordNet
• insertion sort - Яндекс (en-ru)
• insertion sort - Google (en-hu)
• insertion sort - Wikidata
• insertion sort - Wikipédia (angol)