計数下の疑似コードで実装された計数ソート(Counting Sort)の探索を現在と逆順にした場合、安定したソートを保持したままにするにはどの方法が効率がいいでしょうか?
事実、計数ソートこのアルゴリズムでは入力配列を後ろからソートしないと、同じ要素が現れた場合その要素の順番は逆になってしまい、安定したソートではなくなります。
私は。同じ要素が複数回出現した場合に限り、その要素数-1をしたものをそれぞれのカウンターから引けばいいと思ったのですが、その場合はもう一つ余計な配列を用意しなければならず、非効率的ではないかと指摘されました。しかし、それ以外の方法が思いつきません。
なにか手法などありましたら教えていただけると幸いです。
pseudo-code (reference: Algorithm Introduction, MIT Press)
COUNTING-SORT(A,B,k)
C[0..k] を新しい配列とする
for i =0to 0 to k
C[i]=] = 0
for j = 1 to A.length
C[A[j]] = C[A[j]] + 1
//C[i] は i と等しい要素の数を示す.
for i =1to 1 to k
C[i]=] = C[i]+] + C[i−1]
//C[i] は i 以下の要素の数を示す.
for j = A.length downto 1
B[C[A[j]]] = A[j]
12 C[A[j]] = C[A[j]]−1
このアルゴリズムの最後のforループを、for (j = 1 to A.length) にしたいです