Sort Optimisation time

Question

I have 2 sorts:

void sort1(std::vector<int> &toSort)
{
    for(VintIter i=toSort.begin(); i!=toSort.end(); i++)
    {
        for (VintIter j =(toSort.end()-1); j != i; --j)
        {
            if (*(j - 1) > *(j))
            {
                std::iter_swap(j - 1, j);
            }
        }
    }
}

 void sort2(std::vector<int> &toSort)
    {

        for(int i= 0; i<(toSort.size()-1); i++)
        {
            int minElem=i,maxElem=i+1;
            if(toSort[minElem]>toSort[maxElem])
            {
                std::swap(toSort[minElem],toSort[maxElem]);
            }

            while(minElem>0 && toSort[minElem]<toSort[minElem-1])
            {
                std::swap(toSort[minElem],toSort[minElem-1]);
                minElem--;
            }

            while(maxElem<(toSort.size()-1) && toSort[maxElem]>toSort[maxElem+1])
            {
                std::swap(toSort[maxElem],toSort[maxElem+1]);
                maxElem++;
            }

        }

    }

And I'm using QueryPerformanceFrequency and QueryPerformanceCounter to get times of those. For Random vector of 1000 elements for sort1 returns 20.3 and for sort2 5.4. And this is ok.. But when I'm trying to get resoults for sorted array, so for the best situation when the toSort vector is already sorted, the resoults are little weird.. for sort1 it's 12.234 and for sort2 is 0.0213.. For 10 000 elements sort1 is 982.069 and for sort2 is 0.2!

I have assertion for comparing if the vector is sorted. I'm using newest mingw on Windows 7 and windows 8. For i7-5700 HQ and for i5-6300U..

It's only exercise for my to create something better, that have no implementation. I's all about my idea, so i don't want to use std::sort.

My question is: Why second algorithm gives my ~0 time with 10 000 elements?

I assume this is for an exercise in sorting algorithms, or you would (and should) be using [`std::sort`](http://en.cppreference.com/w/cpp/algorithm/sort) instead. — Some programmer dude, Nov 15 '16 at 07:59
And what is your question? Why the numbers for an already sorted vector is so different? How to optimize the first sort? Something else? — Some programmer dude, Nov 15 '16 at 08:01
Cache. The second algorithm is always comparing adjacent elements, so has a much better chance of finding both elements in the L1 (or at least L2) cache. See http://stackoverflow.com/q/11227809/771073 for details. — Martin Bonner supports Monica, Nov 15 '16 at 08:01
Also, almost any N.log N algorithm will outperform any of these N² algorithms. — Martin Bonner supports Monica, Nov 15 '16 at 08:03
*Random vector of 1000 elements* -- Try 100,000 or one million elements. Just using 1000 elements is not nearly enough to show the difference in sorting algorithms. — PaulMcKenzie, Nov 15 '16 at 09:25

score 0 · Accepted Answer · answered Nov 15 '16 at 08:52

0

The first one has complexity of n² in any case.

Whereas in the sorted case, your second algorithm is linear:

toSort[minElem] < toSort[minElem - 1] and toSort[maxElem] > toSort[maxElem+1] is always false, so your inner loop break immediately.

answered Nov 15 '16 at 08:52

Jarod42

203,559
14
181
302

Sort Optimisation time

1 Answers1