stable_sort: ordinea elementelor egale în C++
Înțelege stabilitatea sortării pe înregistrări cu aceeași cheie. Separă păstrarea ordinii inițiale de criteriile explicite ale comparatorului.
În acest material
O sortare este stabilă dacă păstrează ordinea relativă inițială a elementelor echivalente după criteriul de comparare. Cuvântul „echivalente” se referă la comparator, nu neapărat la egalitatea tuturor câmpurilor unei înregistrări.
Un exemplu cu punctaje
Ai în această ordine: Ana cu 8 puncte, Dan cu 10 puncte, Eva cu 8 puncte. Sortezi crescător numai după punctaj. O sortare stabilă păstrează Ana înaintea Evei, deoarece ambele au cheia 8 și Ana apărea prima în intrare.
std::sort nu promite această păstrare. std::stable_sort oferă garanția stabilității. Dacă o anumită rulare a lui sort păstrează accidental ordinea, observația nu devine parte din contractul funcției.
Echivalența depinde de comparator
Pentru comparatorul „punctaj mai mic”, două înregistrări sunt echivalente când nici prima nu precedă a doua, nici a doua nu precedă prima. Numele diferite nu rup egalitatea dacă nu sunt consultate de comparator.
Dacă cerința spune „la punctaje egale, în ordine alfabetică”, trebuie să adaugi numele drept criteriu secundar. Stabilitatea singură păstrează ordinea intrării, care poate fi cu totul alta decât ordinea alfabetică. Citește exact regula de departajare.
Intrarea Ana:8, Dan:10, Eva:8 sortată stabil crescător după punctaj devine Ana:8, Eva:8, Dan:10. Ana rămâne înaintea Evei.Mărește schema ↗
Comparatorul trebuie să rămână strict
Nu înlocui mai mic cu mai mic sau egal pentru a „păstra egalitățile”. Un element nu trebuie să se compare înaintea lui însuși. Comparatorul trebuie să definească o ordine strictă coerentă, indiferent dacă algoritmul ales este stabil.
Pentru două chei, compari mai întâi cheia principală. Numai dacă aceasta este egală treci la cheia secundară. Evită expresii care combină necondiționat comparațiile prin sau, deoarece pot declara simultan că primul element precedă al doilea și invers.
Două sortări succesive
Poți obține o ordine pe două chei sortând mai întâi după cheia secundară, apoi stabil după cheia principală. A doua sortare păstrează ordinea secundară în fiecare grup echivalent al cheii principale. Metoda funcționează datorită stabilității celei de-a doua operații.
Pentru verificare, construiește intenționat trei elemente cu aceeași cheie, dar identificatori diferiți. Urmărește identificatorii înainte și după sortare, nu doar punctajele. Numai astfel observi dacă ordinea relativă cerută este păstrată.
Continuă cu sortarea tablourilor, perechi și iteratori și structuri.
Întrebări frecvente
Ce înseamnă o sortare stabilă?
O sortare care păstrează ordinea relativă inițială a elementelor echivalente după comparator. Dacă Ana și Eva au același punctaj și Ana era prima, o sortare stabilă numai după punctaj păstrează această ordine.
Echivalența după comparator înseamnă că toate câmpurile sunt egale?
Nu. Două înregistrări pot avea nume diferite și totuși să fie echivalente dacă comparatorul folosește numai punctajul lor egal.
Când aleg stable_sort în loc de sort?
Când ordinea inițială a elementelor echivalente face parte din rezultatul dorit. Dacă enunțul cere un al doilea criteriu, exprimă-l explicit în comparator, nu îl presupune din stabilitate.