Kura kārtošanas algoritma tiek izmantots funkcijā sort?

Standarta bibliotēkā C++ funkcija std::sort parasti tiek īstenota, izmantojot Introsort (Introspektīvā šķirošana) algoritmu. Tas ir hibrīds algoritms, kas apvieno:

• Ātru šķirošanu (Quicksort) lielākajā daļā gadījumu
• Heapsort (Kopu šķirošanu), ja rekursijas dziļums kļūst pārāk liels (lai izvairītos no sliktākā gadījuma Quicksort)
• Ievietošanas šķirošanu (Insertion Sort) mazās apakšvirknēs

Introsort nodrošina vidēji labu Quicksort veiktspēju ar garantiju sliktākajā gadījumā O(n log n), pateicoties pārejai uz Heapsort.

Piemērs std::sort izmantošanai:

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {5, 3, 2, 4, 1};
    std::sort(v.begin(), v.end());
    for (int n : v) {
        std::cout << n << ' ';
    }
    return 0;
}

Tādēļ std::sort ir augstas veiktspējas algoritms, kas balstīts uz Introsort.