replace with sort algorithm

[pdk5]

Yes, looks like this is getting more complicated than i thought. (Basically with one array it was simpler to change to std:sort, but second array was added very recently, it gets complicated )

So just exploring, so as you suggested it may not add value.

Thanks a lot again for the inputs and help, i sometimes was going in wrong way (like extracting indices) and correcting me..

[pdk5]

Again,, thanks a lot kaud for the improved solution and help

[wolle]

(Basically with one array it was simpler to change to std:sort, but second array was added very recently, it gets complicated )

If the problem is that you want to co-sort the second array with the first, one way is to introduce a temporary std::vector of std:: pair.

In each std:: pair you combine a PiInfo object with its corresponding MiInfo object. Then the std::vector is sorted according to order you want for PiInfo. Finally the records of the now sorted std:: pairs are copied back into the original arrays.

This solution involves extra copying but copying is O(N) whereas sorting is O(N*logN) so the complexity stays the same. And maybe you can recover some of the copying overhead by selecting the parallel execution policy for std::sort.

[pdk5]

thanks a lot wolle for the comments. Btw as our arrays are huge, so copying may become bottleneck for the performance. And also these structures are not very direct, they are hidden inside lot of templates , so bit messy to do those changes

[2kaud]

our arrays are huge

The code you have will probably give the best performance. In 'simplifying' this, you are likely to have an impact on performance. In these sort of cases, I'd be thinking about performance over 'readability'.

[pdk5]

Thanks kaud

[wolle]

Btw as our arrays are huge, so copying may become bottleneck for the performance. And also these structures are not very direct, they are hidden inside lot of templates , so bit messy to do those changes

Well, what I can see from the code in #1 you are copying already as part of the sorting process (swapping of records),

				{
					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;
					}
				}

If this is the copying we are talking about and the problem is the co-sorting of pIIInfo and pMInfo and speed is inportant then I would suggest the following.

First copy pIIInfo and pMInfo to two temporary std::vectors. Next fill an std:: vector<int> (the index vector) with integers from 0 up to the number of records - 1. Then sort the index vector based on the records of pIIInfo. Finally copy the temporary vectors back to pIIInfo and pMInfo according to the sorted index vector.

Most of the copying and sorting, if not all of it, can be done in parallel by making use of the parallel_policy on containers. Furthermore the sorting swaps just integers and not pIIInfo and pMInfo records as before which should make it faster (especially if the records are large of course).

This should be just a few lines of code using standard containers and standard sorting. The cost of swapping in the sort has been minimized and everything is done in parallel. It should be pretty fast. And finally who knows whether the current sort algorithm implementation is any good? It's hard to get Quicksort right even for an expert.