introsort

Angol

Főnév

introsort (tsz. introsorts)

1. (informatika) Az Introsort (teljes nevén Introspective Sort) egy hibrid rendezési algoritmus, amely három jól ismert módszert ötvöz:

• Quicksort – gyors átlagos esetű teljesítmény,
• Heapsort – garantált ${\textstyle O(n\log n)}$ időbonyolultság a legrosszabb esetben is,
• Insertion sort – gyors kis méretű adathalmazok esetén.

A neve arra utal, hogy introspektív, vagyis figyeli saját viselkedését, és ha a Quicksort túl sok rekurzív lépést tenne (jelezve a legrosszabb esetet), akkor átnyergel Heapsort-ra.

---

⚙️ Miért jó az Introsort?

• Gyors mint a Quicksort a legtöbb gyakorlati esetben,
• Biztonságos mint a Heapsort: elkerüli a ${\textstyle O(n^{2})}$ legrosszabb esetet,
• Hatékony kis tömbökön, ahol Insertion sort váltja ki a Quicksort-ot.

Ez az algoritmus a C++ STL std::sort() függvény alapja a legtöbb modern fordítóban (pl. GCC, LLVM).

---

🏗️ Hogyan működik?

1. Quicksort-al kezd: oszd meg és uralkodj stratégia.
2. Mély rekurzió esetén átvált Heapsort-ra, hogy megelőzze a teljesítményromlást.
3. Kis szegmenseknél Insertion Sort-ot használ, mert az gyorsabb a kis méret miatt.

🎯 A döntési kritérium:

• A maximális rekurzió mélység ${\textstyle =2\cdot \log _{2}(n)}$.
• Ha ezt túllépi, akkor áttér Heapsort-ra.

---

📈 Algoritmus lépések

1. Kezdés: Introsort(A, begin, end, depth_limit)
2. Ha (end - begin) < threshold → Insertion sort
3. Ha depth_limit == 0 → Heapsort
4. Egyébként → válassz pivotot, QuickSort rekurzív hívása bal és jobb részhalmazra
5. A rendezés végén a maradék kis tömbökön Insertion sort

---

🧮 Időbonyolultság

Eset	Bonyolultság
Legjobb eset	${\textstyle O(n\log n)}$
Átlagos eset	${\textstyle O(n\log n)}$
Legrosszabb eset	${\textstyle O(n\log n)}$

Ezért a Quicksort + Heapsort kombinációjával minden esetben garantált a jó teljesítmény.

---

💡 Miért jobb, mint simán a Quicksort?

A sima Quicksort legrosszabb esetben (pl. ha mindig a legkisebb/legnagyobb elemet választja pivotnak) ${\textstyle O(n^{2})}$ időt vehet igénybe.

Az Introsort felismeri, ha ez a helyzet kialakulóban van, és gyorsan vált a Heapsort-ra, amely mindig ${\textstyle O(n\log n)}$.

---

🛠️ Implementáció (pszeudokód)

void introsort(std::vector<int>& arr) {
    int depth_limit = 2 * log2(arr.size());
    introsort_util(arr, 0, arr.size() - 1, depth_limit);
}

void introsort_util(std::vector<int>& arr, int begin, int end, int depth_limit) {
    int size = end - begin + 1;
    if (size < 16)
        insertion_sort(arr, begin, end);
    else if (depth_limit == 0)
        heapsort(arr, begin, end);
    else {
        int pivot = partition(arr, begin, end);
        introsort_util(arr, begin, pivot - 1, depth_limit - 1);
        introsort_util(arr, pivot + 1, end, depth_limit - 1);
    }
}

---

🔎 In-depth: Mikor vált?

A váltás akkor történik, ha a rekurzió mélysége túl nagy, ami azt jelenti, hogy a partíciók túl asszimetrikusak – ez a Quicksort Achilles-sarka.

Az Introsort tehát „önreflexív”: ha úgy látja, hogy baj van, stratégiát vált.

---

💬 Valós használat

• std::sort() C++-ban: introsort alapú.
• LLVM libc++, GNU libstdc++: introsort implementációt használnak.
• Java SE 7+: a Arrays.sort() primitíveken Introsort-szerű viselkedést mutat.

---

🧪 Összehasonlítás más algoritmusokkal

Algoritmus	Átlagos idő	Legrosszabb idő	In-place	Stabil
Quicksort	${\textstyle O(n\log n)}$	${\textstyle O(n^{2})}$	✔️	❌
Heapsort	${\textstyle O(n\log n)}$	${\textstyle O(n\log n)}$	✔️	❌
Mergesort	${\textstyle O(n\log n)}$	${\textstyle O(n\log n)}$	❌	✔️
Introsort	${\textstyle O(n\log n)}$	${\textstyle O(n\log n)}$	✔️	❌

---

📦 Összefoglalás

Az Introsort:

• Hibrid, robusztus, gyors,
• Gyakorlatban jól működik,
• Fejlettebb, mint a klasszikus rendezések.

Ezért válik alapértelmezetté a modern C++ programokban, és szinte minden általános célú rendezési problémára ideális.

További információk

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