問題タブ [counting-sort]

カウントソートを使用して名前をアルファベット順にソートするのに問題があります。たとえば、アルファベット順にソートし、それに数値入力を追加するとします0001 Alex Smith, Gregory John, Alex Smith, Adam Richard, Alex Ryan。出力は次の順序である必要があります。

アダム・リチャード
アレックス・ライアン
アレックス・スミス
グレゴリー・ジョン

これまでの私のコード:

いろいろなことを読んでいます。ソートのカウントの場合、以下のCコードは正常に機能しますが、時間計算量について質問があります。多くの場所で読んでいるように、実際にはO（N）ではありませんが、O（入力配列の最大値-配列の最小値）です。これはNより大きくなる可能性があります。ここで、Nを増やし、同時にmax --minを増やす（範囲-つまり、maxを増やし、minを減らす）と、実行時の複雑さは2次式、つまりO（N ²）になることができますか？または、この種の最悪のケースは、入力配列に同じ値の複数のインスタンスがある場合です。理解しようとするのは本当に明確ではありません。

counting_sortに渡される特定の配列の最小値と最大値を計算したと仮定します。nは入力配列の長さです

基数、カウント、およびバケットソートの定義を読んでいますが、それらはすべて以下のコードにすぎないようです:

私は正しくないことを知っているので、何が欠けているのでしょうか? Java または C での説明に役立つと思われる場合は、コードを示してください。

疑似コードからカウントソートアルゴリズムを実装しました。疑似コードではC[A[j]]、最初のパスの後に最後のループが減少します。これはすべてを右にシフトしていたので、最初のパスの前にデバッグしてデクリメントし、正しい結果を生成しました。しかし、それが機能する以外に理由がわかりません。なぜ、後ではなく前に減らさなければならないのですか。

後にデクリメントした結果は次のとおりです。

そして、前にデクリメントすると：

明らかに、最初はすべてが右にずれていたので、すべてを左に移動しましたが、そもそも正しい位置合わせにならないのはなぜですか?

これが私のカウントソートプログラムです：

入力：

100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 27 6 8 7 29 30 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 7 7 7 2 9 32 33

期待される出力:

1 1 3 3 6 8 9 9 10 12 13 16 16 18 20 21 21 22 23 24 25 25 25 27 27 30 30 32 32 32 33 33 33 34 39 39 40 40 41 42 43 44 44 4 5 3 6 50 57 59 60 61 63 65 67 67 68 69 69 69 69 70 70 73 73 74 75 75 76 78 78 79 79 80 81 82 82 83 83 84 85 86 86 87 87 89 89 89 89 90 90 91 92 94 94 98 98 98 99 99 99

実際の出力:

1 1 3 3 6 8 9 9 10 12 13 16 16 18 20 21 21 22 23 24 25 25 25 27 27 30 30 32 32 32 33 33 33 34 39 39 40 40 41 42 43 44 44 4 5 3 6 50 57 59 60 61 65 67 67 68 69 69 69 70 70 73 73 74 75 75 76 78 78 79 79 80 81 81 82 83 83 84 85 86 86 87 87 89 89 89 90 90 9 9 9 9 82 90 9 9 9

私が得ている出力には、桁が1つありません63。この問題を修正することはできません。

私はソート機能を持っています：

問題は別の場所にあるため、並べ替えアルゴリズムの詳細は省略しました。問題は、 の宣言に問題がありarrayCopyます。

オンライン

このエラーメッセージが表示されます

宣言の使用法に問題があるに違いありませんがconst、修正方法がわかりません...

このような問題の場合、各整数が 10 ビットで表される整数の配列をソートする方法は? カウントソートを使用できると思いますが、整数と文字列の組み合わせである各項目に問題を少し調整すると、整数値に基づいて配列をソートするように求められますが、これを解決するにはどうすればよいですか?

配列内のすべての要素の上限が特定の数値であることがわかっている場合、カウントソートは線形時間で知られています。一般的な配列を使用する場合、配列を線形時間でスキャンして、配列の最大値を見つけてから、カウントソートを適用することはできませんか?