私の入力が (aでbありc、等しいキーを区別するため) であるとします。
1 6a 8 3 6b 0 6c 4
私の数え方の並べ替えは次のように保存されます（、、および情報を破棄しaますb!! c）
0(1) 1(1) 3(1) 4(1) 6(3) 8(1)
それは私に結果を与えるでしょう
0 1 3 4 6 6 6 8
では、この安定ソートはどのようになっているのでしょうか。「等しいキーを持つレコードの相対的な順序を維持する」方法がわかりません。
説明してください。
カウントソートが安定している理由を理解するには、カウントソートが整数のリストのソートに使用できるだけでなく、キーが整数である要素のリストのソートにも使用でき、これらの要素がソートされることを理解する必要があります。それらのそれぞれに関連付けられた追加情報を持ちながら、それらのキーによって。
要素を追加情報で並べ替えるカウント並べ替えの例は、これを理解するのに役立ちます。たとえば、3 つの株を価格順に並べ替えたいとします。
[(GOOG 3), (CSCO 1), (MSFT 1)]
ここで、株価は整数キーであり、銘柄は関連情報です。
ソートの期待される出力は次のようになります。
[(CSCO 1), (MSFT 1), (GOOG 3)]
(containing both stock price and its name,
and the CSCO stock should appear before MSFT so that it is a stable sort)
これをソートするために counts 配列が計算されます (たとえば、株価は 0 から 3 までしか指定できないとします)。
counts array: [0, 2, 0, 1] (price "1" appear twice, and price "3" appear once)
整数配列をソートするだけの場合は、counts 配列を調べて "1" を 2 回出力し、"3" を 1 回出力すると、それが完了し、その後 counts 配列全体がすべてゼロの配列になります。
しかし、ここではソート出力にも銘柄名を表示したいと考えています。この追加情報を取得するにはどうすればよいでしょうか (counts 配列は既にこの情報を破棄しているようです)。さて、関連付けられた情報は、元の並べ替えられていない配列に格納されます。ソートされていない配列 [(GOOG 3), (CSCO 1), (MSFT 1)] には、銘柄名とその価格の両方が利用可能です。最終的に並べ替えられた配列のどの位置 (GOOG 3) が必要かがわかれば、この要素を並べ替えられた配列の並べ替えられた位置にコピーできます。
並べ替えられた配列内の各要素の最終的な位置を取得するには、整数配列の並べ替えとは異なり、counts 配列を直接使用して並べ替えられた要素を出力しません。代わりに、counts 配列から累積合計配列を計算する追加のステップがあります。
counts array: [0, 2, 2, 3] (i from 0 to 3: counts[i] = counts[i] + counts[i - 1])
この累積合計配列は、現在、最終的に並べ替えられた配列内の各値の位置を示しています。たとえば、counts[1]==2現在、値を持つアイテムをソート済み配列のスロットに1配置する必要があることを意味します。2ndは左からの累積合計であるため、直感的counts[i]に、値の前にいくつの小さい項目があるかを示し、ith値の位置がどこにあるべきかを示しithます。
$1 価格の株が最初に表示された場合は、ソート済み配列の 2 番目の位置に出力され、$3 価格の株が最初に表示された場合は、ソート済み配列の 3 番目の位置に出力されます。$1 株が表示され、その要素がソート済み配列にコピーされた場合、counts 配列内のそのカウントを減らします。
counts array: [0, 1, 2, 3]
(so that the second appearance of $1 price stock's position will be 1)
そのため、ソートされていない配列を後方から繰り返し (これは安定性を確保するために重要です)、counts 配列に従ってソートされた配列内の位置を確認し、それをソートされた配列にコピーできます。
sorted array: [null, null, null]
counts array: [0, 2, 2, 3]
iterate stocks in unsorted stocks from backwards
1. the last stock (MSFT 1)
sorted array: [null, (MSFT 1), null] (copy to the second position because counts[1] == 2)
counts array: [0, 1, 2, 3] (decrease counts[1] by 1)
2. the middle stock (CSCO 1)
sorted array: [(CSCO 1), (MSFT 1), null] (copy to the first position because counts[1] == 1 now)
counts array: [0, 0, 2, 3] (decrease counts[1] by 1)
3. the first stock (GOOG 3)
sorted array: [(CSCO 1), (MSFT 1), (GOOG 3)] (copy to the third position because counts[3] == 3)
counts array: [0, 0, 2, 2] (decrease counts[3] by 1)
ご覧のとおり、配列が並べ替えられた後、counts 配列 ([0, 0, 2, 2]) は、整数の配列の並べ替えのようにすべてゼロの配列にはなりません。counts 配列は、並べ替えられていない配列に整数が何回出現するかを示すために使用されるのではなく、最終的な並べ替えられた配列で要素がどの位置にあるべきかを示すために使用されます。そして、要素を出力するたびにカウントを減らすので、本質的に同じキーの次に出現する要素の最終的な位置を小さくしています。そのため、安定性を確保するために、ソートされていない配列を後方から反復する必要があります。
結論：
各要素にはキーとしての整数だけでなく、いくつかの追加情報が含まれているため、キーが同じであっても、追加情報を使用して各要素が異なることがわかり、安定しているかどうかを判断できます。ソート アルゴリズム (適切に実装されていれば、安定したソート アルゴリズムです)。
参考文献:
カウントソートとその安定性を説明するいくつかの良い資料:
本当に簡単です。各「バケット」の単純なカウンターではなく、リンクされたリストです。
つまり、代わりに
0(1) 1(1) 3(1) 4(1) 6(3) 8(1)
あなたが得る
0(.) 1(.) 3(.) 4(.) 6(a,b,c) 8(.)
(ここ.では、バケット内のアイテムを示すために使用します)。
次に、それらを 1 つの並べ替えられたリストにダンプします。
0 1 3 4 6a 6b 6c 8
つまり、 key を持つアイテムを見つけた場合x、同じキーを持つ他のアイテムと区別する他の情報が含まれている可能性があることを知っていれば、bucket のカウンターをインクリメントするだけではありませんx(余分な情報はすべて破棄されます)。
x代わりに、バケットごとにリンクされたリスト (または、一定時間償却された追加を伴う同様に順序付けられたデータ構造) があり、入力を左から右にスキャンしながら、その項目をバケットのリストの最後に追加します。
したがって、カウンターにO(k)スペースを使用する代わりに、最初は空のリストがあり、その長さの合計はアルゴリズムの「カウント」部分の最後になります。このカウントソートのバリアントは以前と同じです。kO(k)nO(n + k)
ソリューションは完全なカウントソートではなく、関連する値を破棄します。
これが完全なカウントソートアルゴリズムです。
ヒストグラムを計算した後：
0(1) 1(1) 3(1) 4(1) 6(3) 8(1)
累積合計を計算する必要があります。各セルには、その値以下の要素がいくつ含まれます。
0(1) 1(2) 3(3) 4(4) 6(7) 8(8)
ここで、元のリストの最後から始めて、逆方向に進みます。
最後の要素は4です。4以下の要素が4つあります。したがって4、4番目の位置に移動します。のカウンターをデクリメントします4。
0(1) 1(2) 3(3) 4(3) 6(7) 8(8)
次の要素は6cです。6以下の要素が7つありますので6c、7番目の位置に移動します。ここでも、のカウンターをデクリメントします6。
0(1) 1(2) 3(3) 4(3) 6(6) 8(8)
^ next 6 will go now to 6th position
ご覧のとおり、このアルゴリズムは安定ソートです。同じキーを持つ要素の順序は保持されます。
3つの「6」値が区別できる場合は、カウントの並べ替えが間違っています（実際の並べ替えでは値が並べ替えられるだけなので、実際の並べ替えでは行われない値に関する情報が破棄されます）。
3つの「6」値が区別できない場合、入力に3つの区別できない「6」があり、出力に3つあるため、ソートは安定しています。それらが「再注文」されたかどうかについて話すことは無意味です：それらは同一です。
非安定性の概念は、値に順序に関与しない関連情報がある場合にのみ適用されます。たとえば、これらの整数へのポインタを並べ替える場合、異なるアドレスを調べることで、3つの6の「違いを知る」ことができます。次に、特定の種類が安定しているかどうかを尋ねることは意味があります。その場合、整数値に基づくカウントソートは、ポインターのソートにはなりません。ポインタ値に基づくカウントソートは、アドレスではなく整数値で並べ替えます。