計数ソート(Counting Sort)の探索を逆順にした場合、安定したソートを保持したままにするにはどの方法が効率がいいでしょうか?
事実、計数ソートは入力配列を後ろからソートしないと、同じ要素が現れた場合その要素の順番は逆になってしまい、安定したソートではなくなります。
私は。同じ要素が複数回出現した場合に限り、その要素数-1をしたものをそれぞれのカウンターから引けばいいと思ったのですが、その場合はもう一つ余計な配列を用意しなければならず、非効率的ではないかと指摘されました。しかし、それ以外の方法が思いつきません。
なにか手法などありましたら教えていただけると幸いです。
計数ソートを入力順にソートした際の安定性
Avril
- 117
- 8