Sortarea introspectivă sau sortarea introspectivă este un algoritm de sortare propus de David Musserîn 1997. Utilizează sortarea rapidă și comută la sortarea în grămada atunci când adâncimea recursiunii depășește un nivel predeterminat (cum ar fi logaritmul numărului de elemente sortate). Această abordare combină punctele forte ale ambelor metode cu un caz O ( n log n ) cel mai rău caz și o viteză comparabilă cu sortarea rapidă. Deoarece ambii algoritmi folosesc comparații, acest algoritm aparține, de asemenea, clasei de sortare bazată pe comparație .
În quicksort, una dintre operațiile critice este alegerea unui suport (elementul în raport cu care matricea este împărțită). Cel mai simplu algoritm pentru alegerea unei baze - luarea primului sau ultimului element al unei matrice ca suport este plină de un comportament prost asupra datelor sortate sau aproape sortate. Niklaus Wirth a sugerat utilizarea elementului din mijloc pentru a preveni degradarea acestui caz la O( n² ) pe intrări proaste. Mediana a trei algoritm de selecție a suportului alege mijlocul primului, mijlociu și ultimului elemente ale matricei ca suport. Cu toate acestea, deși funcționează bine la majoritatea intrărilor, este totuși posibil să găsiți intrări care încetinesc foarte mult acest algoritm de sortare. Astfel de date pot fi folosite de atacatori. De exemplu, atacatorii pot trimite o astfel de matrice către un server Web pentru a realiza o refuz de serviciu .
Musser a descoperit că pe cel mai prost set de date pentru mediana a trei algoritmi de sortare rapidă (a fost luată în considerare o matrice de 100.000 de elemente), introsortarea este de aproximativ 200 de ori mai rapidă. El a evaluat, de asemenea, efectul de cache în cazul sortării Robert Sedgwick , unde intervalele mici sunt sortate la sfârșit printr-o singură trecere de sortare prin inserție . El a descoperit că această abordare poate dubla numărul de rateuri de cache, dar performanța sa este mult mai bună atunci când se folosește un deque și ar trebui lăsată pe seama bibliotecilor de șabloane, în parte pentru că câștigurile nu sunt mari altfel.
Implementarea de către SGI a Bibliotecii de șabloane standard C++ ( stl_algo.h ) folosește abordarea de control a adâncimii recursiunii a lui Musser pentru sortarea instabilă , trece la heapsort , alege un element fix ca mediană a trei și în cele din urmă aplică algoritmul de sortare prin inserție al lui Knuth pentru secvențele care conțin mai puțin peste 16 elemente.
| Algoritmi de sortare | |
|---|---|
| Teorie | Complexitate O notație Relația de comandă Sortați tipuri durabil Intern Extern |
| schimb valutar | |
| Alegere | |
| inserții | |
| fuziune | |
| Fara comparatii | |
| hibrid | |
| Alte | |
| nepractic | |