I have a small array with 7 elements which can have values from 0 to around 6 (very small numbers). The counting sort is really very efficient with such configuration, but, I have another array to keep track of indexes of the first array. For example:
main array: (initial) {0,3,5,1,0,2,4} secondary array (initial) {0,1,2,3,4,5,6}
main array: (sorted) {5,4,3,2,1,0,0}
secondary array (sorted) {2,6,1,5,3,4,0}
The first array should be sorted the regular way, while the second array’s indexes should correspond to their respected elements in the first array in the end.
How to sort arrays following these rules using countingsort and not bubblesort?
I have a working implementation using bubblesort, but I expect counting sort to work faster with the following set.
First, it seems much better as the comments suggest to just use a structure, containing both elements and their indices: struct item { int value; int index; }. You then sort them using any sort you like using item.value only, and you have indices then sorted for you.
However if you specifically want to use counting sort on given data structures, I'd probably modify this counting sort algorithm from simply counting to storing indices instead. For example, where you normally would store a std::vector counters or std::map<int, int> to keep the number of each value in the array, you can instead use a vector/map of vectors/sets. Here an element at index 0 would store all indices of the original array, where the value was 0. Example using just vectors:
say original_array contains {0,3,5,1,0,2,4}
your new structure:
std::vector<std::vector<int>> counters(7); // one vector for each possible value from 0 to 6
counting:
for (int index = 0; index < original_array.size(); ++index)
{
const int& value_at_index = original_array[index];
counters[value_at_index].push_back(index);
}
in the end your counters is going to contain all the information you need. For each element of the counters array, the number of sub-elements is its frequency, and subelements themselves give you indices of the original items. Also note a property that this is a stable sort, i.e. elements of equal value preserve their indices order. An example of what's inside indices after this:
0:0,4
1:3
2:5
3:1
4:6
5:2
6:-
Hope this helps!