質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.04%

ソート方法について

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 2,993

score 17

次の条件下でデータをソートするとき、もっとも比較回数が少ない方法を教えてください。

・ソート対象となるデータは13個
・変数の名前は、t1,t2,t3....t13と、連番(いらない情報?)
・データに入っているのは、1~136までの乱数。
・数値を比較して、小さい順にt1,t2...に代入

例)(t4まで表記)
      t1...113
      t2...42
      t3...82
      t4...1

なら、
t1...1
t2...42
t3...82
t4...113

としたいです。

言葉が不足でしたら、その旨お伝えください。
具体的に手順を教えて頂けると助かります。
ソート用コマンドを使用することはできません。(言語はbatch)
お願いします。
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

0

ソートアルゴリズムの話であれば,ちょっと調べればいっぱい出てきます.
有名所だと「クイックソート」,「バブルソート」,「マージソート」などがあります.
これらの手順を言語に対応させて記述すればいいのではないでしょうか?

「もっとも比較回数が少ない方法」を一概に決定することはできません.
ソート対象の内容,並び順によっても変化します.

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/08/27 23:57

    内容と並び順は明記したのですが、不足でしょうか?
    複数あることは存じていますが、この条件下での最適な方法が知りたいのです

    キャンセル

  • 2015/08/28 00:26 編集

    並び順に付いては、ほとんどソートされている、逆順になっているなどのデータの中身の事だと思います。PCで発生した擬似乱数を代入しているのであれば実際に中身を見なければ分からない事だと思います。ほとんどソートされているデータならバブルソートが早いのですが・・・それが比較回数が少ないからという話ではありません。データの交換回数が少ないだけです。

    キャンセル

  • 2015/08/28 01:38

    なるほど。説明不足でした。重複の無い疑似乱数です。

    「ほとんどソートされているデータならバブルソートが早い」という理由をご教授願えないでしょうか。場合によってはほとんどソート済みの場合もそこそこあるので。

    キャンセル

0

バッチファイル ですか??
バッチファイルは、プログラミング言語、というよりも既存のツール or コマンドの 起動スクリプト 的な性格のものなので、バッチファイルそのものの機能だけでソートのような処理をすることはお勧めできません!

そこで、いくつか確認させてください。
  • バッチファイルを使う(バッチファイルの活用Tipsを身に着ける)こと自体が目的ですか?
  • 実用性を重要視しますか? それとも学習目的ですか?
  • ターゲットのWindowsのバージョンは?

ソート用コマンドを使用することはできません。(言語はbatch) 

の真意をお尋ねしたいです。
あくまでも「バッチファイルでの処理」に拘らねばならない理由がお有りなら、それはそれで理解できますが、処理環境がWindowsだからという理由だけで「バッチファイルでの処理」しかできないということにはなりません。
お使いのWindowsのバージョンによっては、デフォルトの機能だけで(追加インストールなしに)バッチファイルに変わるより良いアプローチの方法があります。


解決済みになっていないので、追記します。
まず、問題を2つに分ける必要があります。
  1.  どのソートアルゴリズムが適しているか
  2.  具体的に(バッチファイルで)どのように実装するか


《ソートアルゴリズムの選択について》
もっとも比較回数が少ない方法
ということですが、これは純粋に、目的の条件にはどのソートアルゴリズムが適しているかという問題です。
ソートアルゴリズムについては非常に古くから様々な研究がなされており、それを多くの方が解説されているので、そちらを確認されることをお勧めします。

というのは、ソート時の比較回数は、単に要素数だけでなく開始時点の並び順にも大きく左右されることがわかっているからです。
つまり、ご提示頂いた情報だけでは「最適解」を決めることはできません。

分かりやすい解説記事の幾つかをご紹介します。
  ソート速度比較
  ソートの種類

たとえば、一般的に「高速」なアルゴリズムとしてしられているクイックソートですが、「安定でない」とあるように、開始時点のデータの並び順によって性能が大幅に変化します。

また、再帰的な処理の苦手な「バッチファイルで」という制約の元では、単純に「論理的な比較回数」の少ないアルゴリズムが本当に優れているとは言い切れません。
同じ言語を使用していても実装方法で速度に差がでる訳ですから、幾つかのアルゴリズムに絞り込んだら、実際の使用条件の元でベンチマークテストを実施することが、「速さを追求」する上では欠かせないと思います。

《バッチファイルでの実装例》
バッチファイルでの実装に自分でチャレンジしてみようとも思いましたが、既に優れた実装例(ベンチマーク付き)がWebに公開されていますので、今回はそれをご紹介するに留めます。
  挿入ソートとクイックソートの実装例

以上、ご参考になれば幸いです。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/08/28 01:32

    バッチファイルを使うことが目的ではありませんが、バッチファイルでソートをするのが目的です。
    実用性というか、速度重視です
    windows8.1です。

    バッチファイルでゲームプログラミングをしている最中なのです。まあお遊びの一環です。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.04%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る