replace with sort algorithm
Hello,
I see the following code does the sorting , but it looks like very complicated way ( of trying to implement the binary search by itself). I was wondering is there anyway i replace it with the sort algorithm from the standard library ?
Code:
void SortInfo(CS* pS, TECH eTechType, PiInfo* pIIInfo, MiInfo* pMInfo, int h, int y)
{
int i(x), j(y);
const int minIndex = pS->m_piList.GetOffsetFromTechType(eTechType);
const int maxIndex = minIndex + pS->m_piList.GetMaxNumCovCells(eTechType);
const int iMidIndex = ( y + x ) / 2;
const PiInfo v = pIInfo[(size_t)iMidIndex];
do
{
while ( pIIInfo[(size_t)j].IsBetterThan(pSim, v, ALL, eTechType) ) j++;
while ( v.IsBetterThan(pSim, pIIInfo[(size_t)i], ALL, eTechType) ) i--;
if ( i >= j )
{
if ( i != j )
{
PiInfo tmp = pIIInfo[(size_t)i];
pIIInfo[(size_t)i] = pIIInfo[(size_t)j];
pIIInfo[(size_t)j] = tmp;
if (pMInfo != nullptr)
{
MiInfo multi = pMInfo[(size_t)i];
pMInfo[(size_t)i] = pMInfo[(size_t)j];
pMInfo[(size_t)j] = multi;
}
}
i--;
j++;
}
} while (j <= i);
if (y < i) SortInfo(pSim, eTechType, pIIInfo, pMInfo, y,i);
if (j < x) SortInfo(pSim, eTechType, pIIInfo, pMInfo, j,x);
}
Thanks a lot for the help and inputs
thanks
pdk
Re: replace with sort algorithm
This looks like a quicksort.
It seems to be be sorting pIIInfo. To use std::sort, you need to specify the begin and end iterator and define an operator<(a, b).
Where does pMInfo fit into this? std::sort will only sort one container, not two. If pMinfo needs to mirror the contents of pIIInfo, then no.
Re: replace with sort algorithm
Thanks a lot, kaud . Btw, i tried following. Not tested fully. But yes, it is only for one array. I m thinking of using transform for second array (not sure)
Code:
std::qsort(&pIIInfo[minIndex], &pIIInfo[maxIndex], [pS, eTechType] (PiInfo & x, PiInfo & y)
{
if(x.IsBetterThan(pS, y, ALL, eTechType))
{
return true;
}
else
return false;
});
Basically, pMInfo is also array of different structure, but array needs to be swapped, only if the pIIInfo is swapped. Basically, the pIIInfo array determines if index, index+1 needs to be swapped for both arrays.
Sorry for the names are bit meaningless, as i didnot want to share my exact work code ..
Re: replace with sort algorithm
But if you sort pIIInfo, then you won't know which pMInfo elements need to be swapped - will you?
Re: replace with sort algorithm
Thanks kaud, yes, i.e true. Not sure , how i can get the info, if first is swapped, do the same for second array !
Re: replace with sort algorithm
In the following program, basically, i am seeing if i can extract the indices of sort algorithm
Code:
#include "stdafx.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
int main()
{
std::vector<int> A = { 5,6 };
std::sort(std::begin(A), std::end(A),
[&](const int& t1, const int& t2)
{
int index1(0), index2(0);
//std::cout << &t1 << "\n" << A.data() << "\n" << sizeof(std::string);
std::cout << "&t1 " << &t1 << "\n";
std::cout << "&t2 " << &t2 << "\n";
std::cout << "A.data()" << A.data() << "\n";
std::cout << "&A[0]" << &A[0] << "\n";
std::cout << "&A[1]" << &A[1] << "\n";
///
});
return 0;
}
It is very strange that &t2 = &A[0], but &t1 is not equal to &A[1]
Re: replace with sort algorithm
Not really. t1 stored in stack space and not heap space - so t1 is a ref to a temp variable used in the sort algorithm.
Re: replace with sort algorithm
As t2 and t1 hold values 5 and 6. I thought they point to original vector address as they are passed as reference !
Re: replace with sort algorithm
Re: replace with sort algorithm
Quote:
Originally Posted by
2kaud
Nope.
Thanks a lot kaud. I was trying to see if i can extract the indices, looks like its getting more complicated than i thought
Re: replace with sort algorithm
AFAIK, you can't. You can't assume anything about sort/qsort other than the provided function will get 2 values to compare. Even if somehow you found something, that may well change with the next issue of the compiler. Anything which isn't a published interface can't be relied upon to remain the same across versions - or across different compilers.
Re: replace with sort algorithm
Thanks a lot kaud. Yes as you adviced, looks like i cant rely on extracting indexes.
While googling i found, another approach was to combine two arrays into one. But in my case, arrays are huge, so that may have performance issues
Re: replace with sort algorithm
Was trying to use the boost zip iterator to combine the two iterators: std::for_each works, but sort is giving me compile error :(
Code:
#include "stdafx.h"
#include <iostream>
#include <boost/iterator/zip_iterator.hpp>
#include <boost/tuple/tuple.hpp>
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> v1{ 4, 3, 2, 1 }, v2{ 10,20,30,40 };
std::sort(boost::make_zip_iterator(boost::make_tuple(std::begin(v1), std::begin(v2))),
boost::make_zip_iterator(boost::make_tuple(std::end(v1), std::end(v2))),
[] (boost::tuple<int&, int&> i, boost::tuple<int&, int&> j )
{
return i.get<0>() < j.get<0>();
}
);
/*
std::for_each(
boost::make_zip_iterator(boost::make_tuple(v1.begin(), v2.begin())),
boost::make_zip_iterator(boost::make_tuple(v1.end(), v2.end())),
[](boost::tuple<int, int> const& tup) {
std::cout
<< boost::get<0>(tup)
<< ", "
<< boost::get<1>(tup)
<< std::endl;
}
);
*/
return 0;
}
Re: replace with sort algorithm
Sorry I can't help with this as I don't use boost.
But as a comment, aren't you in danger of replacing something 'complicated' with something that's could be equally as complicated with a worst performance?
Re: replace with sort algorithm
For the original SortInfo(), this can be a little simplifed:
Code:
void SortInfo(CS* pS, TECH eTechType, PiInfo* pIIInfo, MiInfo* pMInfo, size_t x, size_t y)
{
const size_t minIndex = pS->m_piList.GetOffsetFromTechType(eTechType);
const size_t maxIndex = minIndex + pS->m_piList.GetMaxNumCovCells(eTechType);
const size_t iMidIndex = (y + x) / 2;
const PiInfo v = pIInfo[iMidIndex];
size_t i(x), j(y);
do {
for (; pIIInfo[j].IsBetterThan(pSim, v, ALL, eTechType); j++);
for (; v.IsBetterThan(pSim, pIIInfo[i], ALL, eTechType); i--);
if (i >= j) {
if (i != j) {
std::swap(pIIInfo[i], pIIInfo[j]);
if (pMInfo != nullptr)
std::swap(pMInfo[i], pMInfo[j]);
}
--i;
++j;
}
} while (i <= j);
if (y < i) SortInfo(pSim, eTechType, pIIInfo, pMInfo, y, i);
if (j < x) SortInfo(pSim, eTechType, pIIInfo, pMInfo, j, x);
}