問題タブ [sorting]

多くの場合、辞書（キーと値で構成される）を値で並べ替える必要があります。たとえば、頻度別に並べ替えたい単語とそれぞれの頻度のハッシュがあります。

SortedList単語にマップし直したい単一の値（たとえば頻度）に適したものがあります。

SortedDictionaryは、値ではなくキーで並べ替えられます。カスタムクラスに頼る人もいますが、よりクリーンな方法はありますか？

有向グラフを「シリアル化」する単純なアルゴリズムを探しています。特に、実行順序に相互依存関係がある一連のファイルがあり、コンパイル時に正しい順序を見つけたいと考えています。私はそれがかなり一般的なことであるに違いないことを知っています-コンパイラは常にそれを行います-しかし、私のgoogle-fuは今日弱いです。このための「頼りになる」アルゴリズムは何ですか?

私は最近、いくつかの基本事項をブラッシュアップしていて、リンクリストのマージソートがかなり良い課題であることに気づきました。優れた実装がある場合は、ここでそれを披露してください。

疑似言語で定義された単純な関数があるとしましょう。

ソートされていない数値のリストと、昇順または降順のソート順を指定するブール値を渡します。その見返りに、ソートされた数値のリストを取得します。

私の経験では、境界条件を捉えるのが得意な人もいます。問題は、「テストケースのキャプチャが「完了」したことをどのようにして知るか」です。

今すぐケースのリストを開始できます。賢い人の中には、間違いなく、これまでのどのケースでもカバーされていない「もう1つの」ケースを考える人もいます。

を使用して配列を昇順にソートしたいと思いますC/C++。結果は、要素インデックスを含む配列です。各インデックスは、並べ替えられた配列内の要素の位置に対応しています。

例

編集:シェルソート手順を使用しています。重複値のインデックスは、元の配列の最初にある重複値に基づいて任意に選択されます。

アップデート：

最善の努力にもかかわらず、ポインターの配列の並べ替えアルゴリズムを実装できませんでした。現在の例はコンパイルされません。

誰かが何が悪いのか教えてもらえますか?

助けていただければ幸いです。

それで、今日、私は興味深い問題に遭遇しました。IListを返すWCFWebサービスがあります。並べ替えるまでは大したことではありません。

IListインターフェイスにはsortメソッドが組み込まれていないことがわかりました。

私はArrayList.Adapter(list).Sort(new MyComparer())問題を解決するためにこの方法を使用することになりましたが、それは私には少し「ゲットー」のように見えました。

私は拡張メソッドを作成し、IListから継承し、独自のSort（）メソッドを実装し、リストにキャストすることをいじくりまわしましたが、これらはどれも過度にエレガントに見えませんでした。

だから私の質問は、誰かがIListをソートするためのエレガントな解決策を持っているかということです

私は自分のアミューズメント用に O(n!) ソートを作成しました。これは、完全に置き換えずに高速に実行するために簡単に最適化することはできません。[いいえ、ソートされるまでアイテムをランダム化しただけではありません]。

時間の複雑さを軽減するために引き抜くことができる無関係なジャンクを追加するだけでなく、さらに悪い Big-O ソートを作成するにはどうすればよいでしょうか?

http://en.wikipedia.org/wiki/Big_O_notationには、さまざまな時間の複雑さが大きくなる順に並べられています。

編集:コードを見つけました。これは、リストのすべての組み合わせのリストを生成する面白いハックを使用した O(n!) 決定論的ソートです。反復可能な組み合わせを返す get_all_combinations の少し長いバージョンがありますが、残念ながら単一のステートメントにすることはできませんでした。[以下のコードでタイプミスを修正し、アンダースコアを削除して、バグが発生していないことを願っています]

同じ入力で同じ並べ替えコマンドを使用すると、異なるマシンでは異なる結果が生成されます。どうすれば修正できますか？

DB側のページネーションを持つ大規模なデータベースがあります。これは迅速で、数百万のレコードからわずか 1 秒で 50 行のページを返します。

ユーザーは、基本的にソートする列を選択して、独自のソートを定義できます。列は動的です - 数値、日付、テキストを持つものがあります。

ほとんどの場合、テキストは期待どおりにソートされますが、愚かな方法でソートされます。それはコンピューターにとっては理にかなっていますが、ユーザーを苛立たせます。

たとえば、文字列レコード ID で並べ替えると、次のようになります。

...等々。

これに番号を考慮してもらいたいので、次のようにします。

入力を制御できず (そうでなければ先頭の 000 でフォーマットするだけです)、単一のフォーマットに頼ることもできません - いくつかは "{alpha code}-{dept code}-{rec id}" のようなものです。

C# でこれを行ういくつかの方法を知っていますが、すべてのレコードをプルダウンしてソートすることはできません。

Sqlサーバーで自然な並べ替えをすばやく適用する方法を知っている人はいますか?

私たちは使用しています：

そして、それによってページングしています。

トリガーを追加することはできますが、追加することはできません。彼らの入力はすべてパラメータ化されていますが、形式を変更することはできません.「rec2」と「rec10」を入力すると、そのように自然な順序で返されることを期待しています.

クライアントごとに異なる形式に従う有効なユーザー入力があります。

rec1、rec2、rec3、... rec100、rec101

別の可能性があります: grp1rec1、grp1rec2、... grp20rec300、grp20rec301

入力を制御できないというのは、ユーザーにこれらの標準を変更するよう強制できないという意味です。これらの標準には grp1rec1 のような値があり、それを grp01rec001 として再フォーマットすることはできません。外部システムへのリンク。

これらの形式はさまざまですが、多くの場合、文字と数字が混在しています。

これらを C# で並べ替えるのは簡単です。それを分割して{ "grp", 20, "rec", 301 }、シーケンス値を順番に比較するだけです。

ただし、何百万ものレコードがあり、データがページングされている可能性があるため、SQL サーバーで並べ替えを行う必要があります。

SQLサーバーは比較ではなく値でソートします-C＃では値を分割して比較できますが、SQLでは一貫してソートする単一の値を（非常に迅速に）取得するロジックが必要です。

@moebius - あなたの答えはうまくいくかもしれませんが、これらすべてのテキスト値にソートキーを追加するのは醜い妥協のように感じます.

さまざまなプログラミング言語で文字列の配列を自然に並べ替えるにはどうすればよいですか? 実装とそれがどの言語であるかを回答に投稿してください。