How to return the sorted indices for Counting Sort?

Question

I want to return the sorted indices for x array from the Counting Sort algorithm below, it must be simple but I can not figure out how to do that! Can someone please guide me on how to do that in Matlab or Golang or any idomatic c-style demonstration for the algorithm below? thanks a lot in advance.

x=[6 2 5 3 2 2 ];
MAX=10;
n = length(x);
C = zeros(MAX,1); // intialize counting array 
for j = 1:n
    C(x(j)) = C(x(j)) + 1;
end

z=1;
sorted_x = zeros(n,1);  // empty array -container for sorted elements
for j = 1:n;
   while ( C(j) >0)
      sorted_x(z) = j;
      z=z+1;
      C(j) = C(j) - 1;
   end
end

the code above returns the sorted_x=[2 2 2 3 5 6] But I want to modify it to also return the sorted_indices=[2 5 6 4 3 1]

Thanks

Answer 1

You can use a map to store the indices -

package main
import "fmt"

func main(){
    nums := [6]int{6, 2, 5, 3, 2, 2}
    count := make(map[int][]int)
    for i, v := range nums {
        count[v] = append(count[v], i+1)
    }
    output := []int{}
    for i := 0; i < 10; i++ {
        output = append(output, count[i]...)
    }
    for i := 0; i < len(output); i++ {
        fmt.Printf("%d ", nums[output[i]-1])
    }
    fmt.Println()
    fmt.Println("The indices are:")
    fmt.Println(output)
}

Output -

2 2 2 3 5 6 
The indices are:
[2 5 6 4 3 1]