cabin

0 @title: Index sort

1 @date: 2025-01-12

2 @language: en

3 @categories: c++, algorithms, leetcode

4

5

6 # Index sort

7

8 Today I am going to share my all-time favorite algorithm with a lot of

9 flexibility and use cases. Say for example you need to sort an array but also

10 need to keep track of the original index for each element, or there are

11 multiple arrays that need to be sorted on the same criteria. This is where

12 index sorts steps in.

13

14

15 ## Algorithm

16

17 ```c++

18 #include <vector> // vector

19 #include <algorithm> // sort

20 #include <numeric> // iota

21

22 void do_something(const std::vector<int>& vec) {

23 const int n = vec.size();

24

25 static int idxs[100001];

26 std::iota(idxs, idxs + n, 0);

27 std::sort(idxs, idxs + n, [&](int i, int j) {

28 return vec[i] < vec[j];

29 });

30

31 ...

32 }

33

34 void do_something(const std::vector<int>& vec1, std::vector<int>& vec2) {

35 const int n = vec1.size(); // vec1.size() == vec2.size()

36

37 static int idxs[100001];

38 std::iota(idxs, idxs + n, 0);

39 std::sort(idxs, idxs + n, [&](int i, int j) {

40 return vec1[i] != vec1[j] ? vec1[i] < vec1[j] : vec2[i] < vec2[j];

41 }); // sort based on vec1, or on vec2 if equal

42

43 ...

44 }

45

46 ```

47

48 The main idea of the algorithm is that instead of sorting the array itself, we

49 make a separate array that will represent all of the indices into the original

50 array, and then we sort them instead. Here are the steps:

51

52 1) In the examples above I've created a static array idxs, since I know the

53 maximum value of N. If that isn't the case a dynamic vector can be used

54 instead.

55 2) With the std::iota I fill the idxs array with numbers from 0 to n - 1

56 3) Use std::sort on idxs array with a custom comparator function, that indexes

57 into the original array(s). The result is an array of indices that is

58 rearranged in a way that represents the order that the original array

59 should be in order for it to be sorted.

60

61 The following snippets can be used to index both original and sorted array in

62 the way you see fit.

63

64 ```C++

65 for (int i = 0; i < n; i++) {

66 const int j = idxs[i];

67 // i - position in the sorted array

68 // j - position in the original array

69 }

70 ```

71

72 ```C++

73 #include <span> // C++20

74

75 for (const int i: std::span(idxs, n)) {

76 // iterate over indices in original array, in sorted order

77 }

78 ```

79

80

81 ## Interesting Usage

82

83 ### Minimum number of swaps to make array sorted

84

85 ```C++

86

87 ...

88

89 int res = 0;

90 for (int i = 0; i < n; i++) {

91 while (idxs[i] != i) {

92 swap(idxs[i], idx[idx[i]]);

93 res++;

94 }

95 }

96

97 return res;

98 ```

99

100 This cute algorithm can be used to determine the number of swaps needed to sort

101 an array. It's complexity is O(n), but since we had to sort the index array

102 first, overall complexity is O(sort).

103

104 It leverages the fact that in one swap we can put the element in it's place,

105 since we know where it belongs. Element at position i, belongs at position

106 idxs[i], so we swap it with the element at position idxs[idxs[i]], to get it in

107 place. We repeat this procedure until the current position is satisfied, then

108 we go to the next position.

109

110

111 ### Range compression

112

113 ```C++

114

115 ...

116

117 int cnt = 0;

118 vector<int> compressed(n);

119 for (int i = 1; i < n; i++) {

120 if (idxs[i] != idxs[i - 1]) cnt++;

121 compressed[idxs[i]] = cnt;

122 }

123

124 ```

125

126 Sometimes we don't care about the values themselves, but about their relation

127 to one another (greater, less and equal). We can use this trick to compress the

128 range of values of any size, to the one sized at most N, for later use with some

129 special data structure like Segment Tree.

130