cabin

Source code for personal website

git clone git://git.dimitrijedobrota.com/cabin.git

IndexSort.md (3470B)

1 @title: Index sort 2 @date: 2025-01-12 3 @language: en 4 @categories: c++, algorithms, leetcode 5 6 7 # Index sort 8 9 Today I am going to share my all-time favorite algorithm with a lot of 10 flexibility and use cases. Say for example you need to sort an array but also 11 need to keep track of the original index for each element, or there are 12 multiple arrays that need to be sorted on the same criteria. This is where 13 index sorts steps in. 14 15 16 ## Algorithm 17 18 ```c++ 19 #include <vector> // vector 20 #include <algorithm> // sort 21 #include <numeric> // iota 22 23 void do_something(const std::vector<int>& vec) { 24 const int n = vec.size(); 25 26 static int idxs[100001]; 27 std::iota(idxs, idxs + n, 0); 28 std::sort(idxs, idxs + n, [&](int i, int j) { 29 return vec[i] < vec[j]; 30 }); 31 32 ... 33 } 34 35 void do_something(const std::vector<int>& vec1, std::vector<int>& vec2) { 36 const int n = vec1.size(); // vec1.size() == vec2.size() 37 38 static int idxs[100001]; 39 std::iota(idxs, idxs + n, 0); 40 std::sort(idxs, idxs + n, [&](int i, int j) { 41 return vec1[i] != vec1[j] ? vec1[i] < vec1[j] : vec2[i] < vec2[j]; 42 }); // sort based on vec1, or on vec2 if equal 43 44 ... 45 } 46 47 ``` 48 49 The main idea of the algorithm is that instead of sorting the array itself, we 50 make a separate array that will represent all of the indices into the original 51 array, and then we sort them instead. Here are the steps: 52 53 1) In the examples above I've created a static array idxs, since I know the 54 maximum value of N. If that isn't the case a dynamic vector can be used 55 instead. 56 2) With the std::iota I fill the idxs array with numbers from 0 to n - 1 57 3) Use std::sort on idxs array with a custom comparator function, that indexes 58 into the original array(s). The result is an array of indices that is 59 rearranged in a way that represents the order that the original array 60 should be in order for it to be sorted. 61 62 The following snippets can be used to index both original and sorted array in 63 the way you see fit. 64 65 ```C++ 66 for (int i = 0; i < n; i++) { 67 const int j = idxs[i]; 68 // i - position in the sorted array 69 // j - position in the original array 70 } 71 ``` 72 73 ```C++ 74 #include <span> // C++20 75 76 for (const int i: std::span(idxs, n)) { 77 // iterate over indices in original array, in sorted order 78 } 79 ``` 80 81 82 ## Interesting Usage 83 84 ### Minimum number of swaps to make array sorted 85 86 ```C++ 87 88 ... 89 90 int res = 0; 91 for (int i = 0; i < n; i++) { 92 while (idxs[i] != i) { 93 swap(idxs[i], idx[idx[i]]); 94 res++; 95 } 96 } 97 98 return res; 99 ``` 100 101 This cute algorithm can be used to determine the number of swaps needed to sort 102 an array. It's complexity is O(n), but since we had to sort the index array 103 first, overall complexity is O(sort). 104 105 It leverages the fact that in one swap we can put the element in it's place, 106 since we know where it belongs. Element at position i, belongs at position 107 idxs[i], so we swap it with the element at position idxs[idxs[i]], to get it in 108 place. We repeat this procedure until the current position is satisfied, then 109 we go to the next position. 110 111 112 ### Range compression 113 114 ```C++ 115 116 ... 117 118 int cnt = 0; 119 vector<int> compressed(n); 120 for (int i = 1; i < n; i++) { 121 if (idxs[i] != idxs[i - 1]) cnt++; 122 compressed[idxs[i]] = cnt; 123 } 124 125 ``` 126 127 Sometimes we don't care about the values themselves, but about their relation 128 to one another (greater, less and equal). We can use this trick to compress the 129 range of values of any size, to the one sized at most N, for later use with some 130 special data structure like Segment Tree. 131