Filip Rynkowski Filip Rynkowski - 17 days ago 8
C++ Question

Sort Optimisation time

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?

Answer

The first one has complexity of 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.

Comments