რა ალგორითმი გამოიყენება sort ფუნქციაში?

C++ სტანდარტული ბიბლიოთეკის ფარგლებში, ფუნქცია std::sort ჩვეულებრივ იშლება Introsort (ინტროსპექტიული სორტირება) ალგორითმის გამოყენებით. ეს არის ჰიბრიდული ალგორითმი, რომელიც აერთიანებს:

• სწრაფ სორტირებას (Quicksort) უმეტეს შემთხვევებში
• Heapsort (კოშკის სორტირება), თუ რეკურსიის სიღრმე ძალიან დიდია (სწორად თავიდან აიცილოს Quicksort-ის ყველაზე უარესი შემთხვევა)
• Insertion Sort (ჩასმის სორტირება) მცირე ქვემასივებისთვის

Introsort უზრუნველყოფს საშუალოდ კარგი შესრულებას სწრაფ სორტირებაზე და გаранტია ყველაზე უარესი შემთხვევა O(n log n), რომელიც ხდება Heapsort-ზე გადასვლით.

მაგალითი std::sort-ის გამოყენების:

#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;
}

ამიტომ, std::sort არის მაღალი ეფექტურობის ალგორითმი, რომელიც დაფუძნებულია Introsort-ზე.