66245


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

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

[code]

    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
    
[/code]

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


CC BY-SA 4.0
2020-05-03T05:59:30.757
66235
2020-05-04T23:25:53.940
2020-05-03T09:24:44.820
19110
38330
question
c アルゴリズム データ構造
計数ソートを入力順にソートした際の安定性


このアルゴリズムでは最後のループが回る直前の `C[i]` の値が、配列 `B` における値 `i` の **末尾**
のインデックスを示すように計算されています。このため最後のループでは配列 `A` を **後ろ** から走査する形が自然です。

逆に考えると、最後のループで配列 `A` を **前** から走査したければ、`C[i]` の値が配列 `B` における値 `i` の **先頭**
のインデックスを示すように計算すれば良いです。

これを計算するやり方はいくつかあると思いますが、たとえば以下のようにできます。

[code]

    COUNTING-SORT(A, B, k)
    C[0..(k + 1)] を新しい配列とする
    for i = 0 to (k + 1)
        C[i] = 0
    for j = 1 to A.length
        C[A[j] + 1] = C[A[j] + 1] + 1
        //C[i + 1] は i と等しい要素の数を示す．
    for i = 1 to k
        C[i] = C[i] + C[i−1]
        //C[i] は i 未満の要素の数を示す (i ∈ {1..k})．
    for j = 1 to A.length
        C[A[j]] = C[A[j]] + 1
        B[C[A[j]]] = A[j]
    
[/code]


CC BY-SA 4.0
2020-05-03T10:00:03.063
66245
2020-05-04T17:32:04.463
2020-05-04T17:32:04.463
19110
19110
66235
answer


**分布数え上げソートのC言語による実装**  
計数ソート(Counting Sort)を調べてみたところ、次のページが見つかりました。

  * [分布数え上げソート [Counting Sort]](https://www.codereading.com/algo_and_ds/algo/counting_sort.html)
  * [分布数え上げソートのデモンストレーション・プログラム: counting_sort.c](https://www.codereading.com/algo_and_ds/algo/source/counting_sort.c)

質問された方の疑似コードとデモンストレーション・プログラムに以下の違いがあります。

  * 疑似コード  
A と B は 1-indexed、C は 0-indexed

  * デモンストレーション・プログラム  
C言語で実装しているため、A B Cはすべて0-indexed、ただしCは最初の要素を使用せず、 1-indexedのように使っています。  
このため疑似コードの(1)と(2)は、デモンストレーション・プログラムでは順序が逆になっています。

[code]

    for j = A.length downto 1 
        B[C[A[j]]] = A[j]     ・・・・・（１）
        C[A[j]] = C[A[j]]−1 　・・・・・（２）
    
[/code]

**入力配列を後ろからソートするアルゴリズム**  
nekketsuuu♦さんの回答(前から)とのアルゴリズムと質問された方のアルゴリズム(後ろから)の振る舞いを比較しました。双方とも安定なソートであることが確認できました。

比較にした入力データaは{8,4,10,3,8,5}です。  
双方のアルゴリズムとも`a[1]`の8が`b[4]`に格納され、`a[5]`の8が`b[5]`に格納されています。

【前から処理】

[code]

    b[4] = a[1]:8
    b[2] = a[2]:4
    b[6] = a[3]:10
    b[1] = a[4]:3
    b[5] = a[5]:8
    b[3] = a[6]:5
    
    
[/code]

【後ろから処理】

[code]

    b[3] = a[6]:5
    b[5] = a[5]:8
    b[1] = a[4]:3
    b[6] = a[3]:10
    b[2] = a[2]:4
    b[4] = a[1]:8
    
[/code]

* * *

**回答を大幅に修正しました。  
先の回答では質問された方の疑似コードに誤りがあると指摘しましたが誤解でした。  
大変失礼しました、お詫びいたします。**


CC BY-SA 4.0
2020-05-04T06:09:14.580
66273
2020-05-04T23:25:53.940
2020-05-04T23:25:53.940
35558
35558
66235
answer