Skip to main content
「逆」がどっちからどっちなのか分かりにくかったので少し表現を改めました。インデントを直しました。
ソース リンク
nekketsuuu
  • 2.4万
  • 12
  • 53
  • 117

計数下の疑似コードで実装された計数ソート(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) にしたいです

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

pseudo-code (reference: Algorithm Introduction, MIT Press)

COUNTING-SORT(A,B,k) 
C[0..k] を新しい配列とする 
for i =0to k 
C[i]=0 
for j =1 to A.length 
    C[A[j]] = C[A[j]]+1 
    //C[i] は i と等しい要素の数を示す. 
for i =1to 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) にしたいです

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

pseudo-code (reference: Algorithm Introduction, MIT Press)

COUNTING-SORT(A,B,k) 
C[0..k] を新しい配列とする 
for i = 0 to k 
    C[i] = 0 
for j = 1 to A.length 
    C[A[j]] = C[A[j]] + 1 
    //C[i] は i と等しい要素の数を示す. 
for i = 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] 
    C[A[j]] = C[A[j]]−1

このアルゴリズムの最後のforループを、for (j = 1 to A.length) にしたいです

pseudo code の追加
ソース リンク
Avril
  • 117
  • 8

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

pseudo-code (reference: Algorithm Introduction, MIT Press)

COUNTING-SORT(A,B,k) 
C[0..k] を新しい配列とする 
for i =0to k 
C[i]=0 
for j =1 to A.length 
    C[A[j]] = C[A[j]]+1 
    //C[i] は i と等しい要素の数を示す. 
for i =1to 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) にしたいです

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

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

pseudo-code (reference: Algorithm Introduction, MIT Press)

COUNTING-SORT(A,B,k) 
C[0..k] を新しい配列とする 
for i =0to k 
C[i]=0 
for j =1 to A.length 
    C[A[j]] = C[A[j]]+1 
    //C[i] は i と等しい要素の数を示す. 
for i =1to 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) にしたいです

ソース リンク
Avril
  • 117
  • 8

計数ソートを入力順にソートした際の安定性

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