C++STL sort 정렬 내부 메커니즘 - Apple의 학습 노트

STL sort 구현 원리:

STL의sort는 일반적인 빠른 정렬이 아니라 일반적인 빠른 정렬을 최적화하는 것 외에 삽입 정렬과 무더기 정렬을 결합시켰다.수량 등급과 상황에 따라 적당한 정렬 방법을 자동으로 선택할 수 있다.데이터의 양이 비교적 많을 때 빠른 정렬을 채택하여 단락을 나누어 귀속한다.일단 세그먼트를 나눈 후의 데이터 양이 어떤 밸브 값보다 작으면 귀속 호출이 너무 큰 추가 부하를 가져오지 않도록 삽입 정렬로 바꿉니다.귀속 단계가 너무 깊으면 최악의 상황이 발생하는 경향이 있고 무더기로 순서를 바꾸기도 한다.
c++11로 vslam을 선택한 이상 STL은 반드시 배워야 한다.바퀴를 만들지 않고 거인의 어깨에 서 있다는 원칙에 따라.물론 STL의 메커니즘을 이해하고 스스로 체험해야만 STL 라이브러리가 확실히 좋은 것인지, 다른 사람이 좋다고 해서 좋은 것인지를 확인할 수 있다.

c++ code

    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    using namespace std;
    /*
    ratio<3600, 1>           hours
    ratio<60, 1>             minutes
    ratio<1, 1>              seconds
    ratio<1, 1000>           milliseconds
    ratio<1, 1000000>        microseconds
    ratio<1, 1000000000>     nanosecons
    */
    #define LEN 10000
    
    int main()
    {
        int n=0;
        int min=0;
        vector v1;
        for( int i = 0; i != LEN; ++i )
        {
            v1.push_back(rand()%10);
        }
        //copy(v1.begin(), v1.end(), v2.begin()); 
        vector v2(v1.begin(), v1.end());   // copy , 
        auto beginTime = chrono::high_resolution_clock::now();
        sort( v1.begin(), v1.end()); // ， STL 
        auto endTime = chrono::high_resolution_clock::now();
        auto elapsedTime= chrono::duration_cast<:milliseconds>(endTime - beginTime);
        cout << "v1:Algorithm elapsed time is " << elapsedTime.count() << " milliseconds" << endl;
    
        beginTime = chrono::high_resolution_clock::now();
        for(int i = 0; i < LEN; i++ )
        {
          min = v2[i];
          for(int j = i; j < LEN; j++ )
          {
            if(v2[j](endTime - beginTime);
        cout << "v2:Algorithm elapsed time is " << elapsedTime.count() << " milliseconds" << endl;
        // For debug
        // for( int i = 0; i != LEN; ++i )
        // {
        //     cout<

출력 결과:

D:\ws\alg_compare\build>main.exe
v1:Algorithm elapsed time is 2 milliseconds
v2:Algorithm elapsed time is 185 milliseconds