Защо кодът ми за сортиране чрез сливане е по-бавен от сортирането чрез вмъкване

Опитвам се да направя сортиране чрез сливане и сортиране при вмъкване и сравнявам резултата от времето и за двете. И от входен размер на масив 10 до 10000 сортирането чрез сливане е по-бавно от сортирането чрез вмъкване

това е кодът за сортиране на вмъкване

vector<int> insertion_sort(vector<int> vec)
{
    for(int i = 1 ; i <vec.size();i++)
    {
        int j = i-1;
        while(j>=0 && vec[j+1]<vec[j] )
        {
            int x = vec[j+1];
            vec[j+1] = vec[j];
            vec[j--] = x;
        }
    }
    return vec;
}

И това е кодът за сортиране на сливане

vector<int> merge(vector<int> left,vector<int> right)
{
    int i = 0;
    int j = 0;
    vector<int> ret(left.size()+right.size());
    int it = 0;
    for(; i <left.size() && j<right.size();)
    {
        if(left[i]<right[j])
            ret[it++]=(left[i++]);
        else if(right[j]<left[i])
            ret[it++]=(right[j++]);
        else ret[it++]=(left[i++]),ret[it++]=(right[j++]);
    }
    for(;i<left.size();)
        ret[it++]=(left[i++]);
    for(;j<right.size();)
        ret[it++]=(right[j++]);
    return ret;
}
vector<int> merge_sort(vector<int> A,int start,int end)
{
    if(start >= end) 
    {
        vector<int> v(1);
        v[0]=(A[start]);
        return v;
    }
    int mid = (start+end )/ 2;
    vector<int> left = merge_sort(A,start,mid);
    vector<int> right = merge_sort(A,mid+1,end);
    return merge(left,right);
}

и накрая така ги извиквам всички и изчислявам времето

int main()
{
    vector<int> rand_vec;

    srand(time(0));
    for(int i = 0 ; i <SIZE;i++)
    {
        rand_vec.push_back(rand()%SIZE);
    }
    int t = clock();
    vector<int> merge_sorted = merge_sort(rand_vec,0,rand_vec.size()-1);
    puts("");
    printf("merge sort time = %d\n",clock() - t );


    t = clock();
    vector<int> insertion_sorted = insertion_sort(rand_vec);
    puts("");
    printf("insertion sort time = %d\n",clock() - t );
    return 0;
}

Искам да знам дали съм направил нещо нередно в този код, за да направя времето за сортиране чрез сливане повече от времето, използвано за сортиране чрез вмъкване.

Благодаря.


person AerRayes    schedule 12.10.2013    source източник
comment
Какво е РАЗМЕР? Ако е малко, това може да е вашият проблем.   -  person templatetypedef    schedule 12.10.2013
comment
Аз съм по-скоро Java човек, но предаването на вектора като параметър не създава ли негово копие (конструктора за копиране)? Това би било тежко.   -  person SJuan76    schedule 12.10.2013
comment
@templatetypedef Опитах SIZE от 5 до 100 000 и всеки път, когато сортирането чрез сливане отнема повече време   -  person AerRayes    schedule 12.10.2013
comment
@SJuan76 И аз се страхувах, че преминаването на вектори може да създаде дилема. в същото време исках да го направя този път с помощта на вектори   -  person AerRayes    schedule 12.10.2013
comment
Вместо vector<int>, използвайте *vector<int> (и съответно променете останалата част от кода).   -  person SJuan76    schedule 12.10.2013
comment
или дори по-добре (const, когато е възможно) справка vector<int>& ;)   -  person lolando    schedule 12.10.2013
comment
и между другото, използвайте reserve за вашия вектор, преди да използвате хиляди push_back, когато знаете размера предварително   -  person lolando    schedule 12.10.2013
comment
@lolando Благодаря. Точно това опитах, след като SJuan76 каза, че и това наистина намали времето драматично.   -  person AerRayes    schedule 12.10.2013
comment
@lolando Преди имах обратно връщане в целия код за сортиране чрез сливане .. след това го замених с [] оператор за по-бърз достъп, след като знаех размера .. но защо да използвам обратен?   -  person AerRayes    schedule 12.10.2013
comment
reserve, а не reverse. Посочете крайния размер, така че векторът да не расте на всеки няколко входа.   -  person SJuan76    schedule 12.10.2013
comment
@SJuan76 строго погледнато, reserve задава капацитета, а не размера   -  person lolando    schedule 12.10.2013


Отговори (4)


за да обобщим предоставените досега отговори:
- използвайте препратка (или указател ), за да избегнете копирането на вектори:
- използвайте reserve, когато знаете размера предварително, преди да използвате хиляди push_back (така че да не е необходимо да преразпределяйте динамично, когато капацитетът е надвишен)
- можете да направите const vector<int>& merge_sorted = ..., за да избегнете копиране при връщане на вашия вектор

person lolando    schedule 12.10.2013
comment
Хората понякога се притесняват от нарастващата постепенно цена на std::vector. Преди се притеснявах за това и използвах reserve(), за да оптимизирам растежа. След като измерих моя код и многократно имах проблеми с намирането на ползите от производителността на reserve() в реални програми, спрях да го използвам, освен когато е необходимо, за да избегна невалидността на итератора (рядък случай в моя код). Отново: измервайте, преди да оптимизирате. – Bjarne Stroustrup (stroustrup.com/bs_faq2.html#slow-containers ) - person rici; 12.10.2013
comment
Не мисля, че резервирането вреди на четимостта или поддръжката на кода. Ако не друго, то документира, че размерът е известен предварително. Може би няма големи ползи, но може и да го направите. - person Teimpz; 29.11.2016

Предаването на вектори по референция, а не по стойност, прави огромна разлика. На моята машина с SIZE=50000, компилиран с -O3, преди:

merge sort time = 5730000

insertion sort time = 1470000

След:

merge sort time = 10000

insertion sort time = 1470000

Промених само два реда:

vector<int> merge(const vector<int> &left,const vector<int> &right)
vector<int> merge_sort(const vector<int> &A,int start,int end) 
person mrip    schedule 12.10.2013

Освен отговора на mrip относно препратките, имайте предвид:

„Сортирането с вмъкване е един от най-бързите алгоритми за сортиране на много малки масиви, дори по-бързо от бързото сортиране. Най-добрият входен случай е масив, който вече е сортиран. В този случай сортирането с вмъкване има линейно време на изпълнение. Най-простият вход в най-лошия случай е масив, сортиран в обратен ред."

person Denes    schedule 12.10.2013

Сортирането чрез сливане не е непременно по-бавно от сортирането чрез вмъкване. Времето, необходимо за сортиране чрез вмъкване за сортиране на 'n' елемента, е пропорционално на n на квадрат (nn), докато времето, необходимо за сортиране чрез сливане, е пропорционално на n пъти log от n база 2 (nlgn) Така че вмъкването сортирането е по-бързо от сортирането чрез сливане в някои кодове, докато сортирането чрез сливане в други

person Swarup Hegde    schedule 29.11.2016