Az introsort vagy introspektív rendezés David Musser által javasolt rendezési algoritmus1997-ben. Gyors rendezést használ , és halomba rendezésre vált, ha a rekurziós mélység meghalad valamilyen előre meghatározott szintet (például a rendezett elemek számának logaritmusát ). Ez a megközelítés mindkét módszer erősségeit egy O ( n log n ) legrosszabb esettel és a gyorsrendezéshez hasonló sebességgel ötvözi. Mivel mindkét algoritmus összehasonlításokat használ, ez az algoritmus is az összehasonlítás alapú rendezési osztályba tartozik .
A gyorsrendezésben az egyik kritikus művelet a támasz kiválasztása (az az elem, amelyre nézve a tömb fel van osztva). A bázis kiválasztásának legegyszerűbb algoritmusa - ha egy tömb első vagy utolsó elemét támasztja alá, az tele van rossz viselkedéssel a rendezett vagy majdnem rendezett adatokon. Niklaus Wirth a középső elem használatát javasolta, hogy megakadályozza, hogy ez az eset O( n ²)-re romoljon rossz bemeneteken. A három támogatás kiválasztási algoritmus mediánja a tömb első, középső és utolsó elemének közepét választja támaszként. Bár a legtöbb bemeneten jól teljesít, még mindig lehet találni olyan bemeneteket, amelyek nagymértékben lassítják ezt a rendezési algoritmust. Az ilyen adatokat potenciálisan felhasználhatják a támadók. Például a támadók egy ilyen tömböt küldhetnek egy webszervernek , hogy szolgáltatásmegtagadást érjenek el .
Musser úgy találta, hogy a három gyorsrendezési algoritmus mediánjának legrosszabb adathalmazán (100 000 elemből álló tömböt vettek figyelembe), az introsort körülbelül 200-szor gyorsabb. Felmérte a gyorsítótár hatását a Robert Sedgwick rendezés esetében is , ahol a kis tartományokat a végén egyetlen beillesztési rendezési lépéssel rendezi . Úgy találta, hogy ez a megközelítés megduplázhatja a gyorsítótár-kihagyások számát, de teljesítménye sokkal jobb deque használata esetén, és a sablonkönyvtáraknál kell hagyni, részben azért, mert a nyereség egyébként nem nagy.
A C++ Standard Template Library ( stl_algo.h ) SGI implementációja Musser rekurziós mélységvezérlési megközelítését használja az instabil rendezéshez , átvált heapsort -re, egy rögzített elemet választ a három mediánjaként, végül a Knuth-féle beillesztési rendezési algoritmust alkalmazza a kevesebbet tartalmazó sorozatokhoz. mint 16 elem.
| Rendezési algoritmusok | |
|---|---|
| Elmélet | Bonyolultság O jelölés Rendelési viszony Típusok rendezése fenntartható Belső Külső |
| Csere | |
| Választás | |
| Betétek | |
| egyesülés | |
| Nincs összehasonlítás | |
| hibrid | |
| Egyéb | |
| nem praktikus | |