-
November 9th, 2020, 08:44 AM
#1
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
-
November 9th, 2020, 12:03 PM
#2
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.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
November 9th, 2020, 12:27 PM
#3
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 ..
Last edited by pdk5; November 9th, 2020 at 12:47 PM.
-
November 9th, 2020, 12:49 PM
#4
Re: replace with sort algorithm
But if you sort pIIInfo, then you won't know which pMInfo elements need to be swapped - will you?
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
November 9th, 2020, 12:56 PM
#5
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 !
-
November 10th, 2020, 11:15 AM
#6
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]
Last edited by pdk5; November 10th, 2020 at 11:20 AM.
-
November 10th, 2020, 12:51 PM
#7
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.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
November 10th, 2020, 02:03 PM
#8
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 !
-
November 10th, 2020, 02:21 PM
#9
Re: replace with sort algorithm
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
November 10th, 2020, 02:42 PM
#10
Re: replace with sort algorithm
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
-
November 11th, 2020, 03:10 AM
#11
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.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
November 11th, 2020, 04:31 AM
#12
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
-
November 11th, 2020, 05:39 AM
#13
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;
}
Last edited by pdk5; November 11th, 2020 at 07:11 AM.
-
November 11th, 2020, 06:54 AM
#14
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?
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
November 11th, 2020, 07:06 AM
#15
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);
}
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|