CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 22

Thread: replace with sort algorithm

  1. #1
    Join Date
    May 2015
    Posts
    356

    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

  2. #2
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,320

    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++17 Compiler: Microsoft VS2019 (16.8.2)

  3. #3
    Join Date
    May 2015
    Posts
    356

    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.

  4. #4
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,320

    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++17 Compiler: Microsoft VS2019 (16.8.2)

  5. #5
    Join Date
    May 2015
    Posts
    356

    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 !

  6. #6
    Join Date
    May 2015
    Posts
    356

    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.

  7. #7
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,320

    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++17 Compiler: Microsoft VS2019 (16.8.2)

  8. #8
    Join Date
    May 2015
    Posts
    356

    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 !

  9. #9
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,320

    Re: replace with sort algorithm

    Nope.
    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++17 Compiler: Microsoft VS2019 (16.8.2)

  10. #10
    Join Date
    May 2015
    Posts
    356

    Re: replace with sort algorithm

    Quote Originally Posted by 2kaud View Post
    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

  11. #11
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,320

    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++17 Compiler: Microsoft VS2019 (16.8.2)

  12. #12
    Join Date
    May 2015
    Posts
    356

    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

  13. #13
    Join Date
    May 2015
    Posts
    356

    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.

  14. #14
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,320

    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++17 Compiler: Microsoft VS2019 (16.8.2)

  15. #15
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,320

    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++17 Compiler: Microsoft VS2019 (16.8.2)

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)