About Sorting with indexes | Life Hack

Правка en1, от SixtyWithoutSchool, 2023-06-27 12:52:16

Heyy!!!!

Today I found something that may be useful to some of you. Maybe most of you already know this.

PS: Lets say you have a vector/array v= {1,3,2,4} and you want to iterate over it in a sorted way and you can't actually change v.

There can be many approaches for such scenario, Some of them I have listed below:

1) Copy v={1,3,2,4} into another vector tmp and then sort it and use.

2) Make an index_cum_value vector<pair<int,int>> v1= {{1,0},{3,1},{2,2},{4,3}} where first element of pair is our value and second element is the index in the original array. You can sort it on the basis of first element to get an sorted array with its original indexes intact. And by sorting on the basis of second element, you can retrieve the original array.

I personally used 2nd approach in most cases but, If you have to handle 3 or 4 array in this manners, you either have to come up with something like vector<pair<pair<pair<x,y>,z>> which is way messy to handle

OR

you can use this:

1) Create an order vector: odr= {0,1,2....n-1} and v= {1,3,2,4}

2) Now you can sort the odr vector with a custom comparator as

sort(odr.begin(),odr.end(), [&](int &i,int &j){ return v[i]<v[j];});

3) Whenever you want to access the elements in sorted order, you can access like v[odr[i]]

4) Doesn't Matter how many vectors you have, All the vectors can be easily addressed with this approach.

You can practice this approach in some of the questions:

Problem 1

Problem 2

That's It! Hope u got to know something new :)

Теги sorting, comparators

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский SixtyWithoutSchool 2023-06-27 12:52:16 1791 Initial revision (published)