- ベストアンサー
アルゴリズム
- みんなの回答 (4)
- 専門家の回答
質問者が選んだベストアンサー
安定な整列法:選択法、挿入法 不安定な整列法:バブル整列法 安定か不安定かは、すでに回答されている通り、同じキーのものが整列後も同じ順番に並んでいるかどうかと言うことです。ご自分で確かめてください。
その他の回答 (3)
- hitomi13
- ベストアンサー率41% (5/12)
No.1のahsblueさんの回答は、処理速度について述べられたものだと思いますが、 選択ソート:データ数のみに依存するため、一定。 挿入ソート ・配列で実装:サーチ法によらず、データの内容に大きく依存。(挿入時のシフトに時間がかかる。逆順列時最大) ・リストで実装:挿入にかかる時間は一定だが、リニアサーチのみになるため、データの内容に少し依存。(正順列時最大) バブルソート:データ内容に大きく依存。(並びの交換に時間がかかる。逆順列時最大) ※ソート完了フラグをつけた場合、正順列ではクイックソートより早い。 です。 参考までに。
- punchan_jp
- ベストアンサー率55% (155/280)
ソーティングで「安定」とは、同じキーをもつ項目の順位がソーティ ング前後で保たれるかという意味ですね。各ソーティング法のどれ が安定かは、たいていのアルゴリズムの教科書に書いてあります。 たとえ書いてなくても、アルゴリズムそのものが理解できていれば、 例題を作って試してみることえ、安定かどうかわかります。 (あまり小さい例を作ると、安定でなくてもたまたま安定に見えた りしますが)
- ahsblue
- ベストアンサー率58% (23/39)
安定の意味が把握しきれませんが・・ 選択法 = 安定 挿入法 = 安定しない バブル = 安定 だと思います。 理由は、選択ソートの判定回数はバブルソートは全体数にのみ依存し、データ内容には依存しない。 挿入法ではデータ内容に依存するためです。 どうでしょうか?
関連するQ&A
- 探索・整列アルゴリズムのメリット・デメリットについ
「コンピューターはなぜ動くのか?」の第5章の「アルゴリズムと仲良くなる7つのポイント」のところにて、主な定番アルゴリズムとして、 表5.1 主な定番アルゴリズム (1)ユーグリットの互除去 (2)エラトステネスのふるい (3)線型探索 (4)2分探索 (5)ハッシュ法 (6)バブル・ソート (7)クイック・ソート 上記のアルゴリズムがあり、そのアルゴリズムの用途には (1)最大公約数のアルゴリズム (2)素数のアルゴリズム (3)データ探索のアルゴリズム (4)整列のアルゴリズム 上記のアルゴリズムがありますが、(3)~(4)のアルゴリズムの用途においてのメリット・デメリット ・データ探索のアルゴリズム (3)線型探索 (4)2分探索 (5)ハッシュ法 についてのメリット・デメリット ・整列のアルゴリズム (6)バブル・ソート (7)クイック・ソート についてのメリット・デメリット これらを教えて頂けばと思っております。 よろしくお願いたします。
- 締切済み
- その他([技術者向] コンピューター)
- ソートアルゴリズム(選択法とバブルソート)の交換回数
バブルソートと選択法について、交換回数がわかりません。 比較回数については、ネットで検索したり、本に載っているので分かりやすいのですが、交換回数があまり載っていなく…。 選択法の交換回数の最大値は、n-1でしょうか? バブルソートの交換回数の最大値は、nでしょうか? 交換回数については、選択法のほうがバブルソートより少なくてすむそうですが、上の答えでいいのかわかりません。 どなたか教えてください。お願いしますm(_ _)m
- 締切済み
- その他([技術者向] コンピューター)
- アルゴリズムに関する問題
こんばんわ、いくつかの問題につまってしまったので解答と簡単な解説をお願いします; 【問1】 4桁の数字( a1a2a3a4 )をハッシュ法を用いて配列に格納したい。 ハッシュ関数をmod( a1 +a2 +a3 +a4 ,5 )とし、求めたハッシュ関数値に対応する位置の配列要素に格納する場合、9576は(ア)~(オ)のどこに入るか。 ここでmod(x,5)の値は、xを5で割った余りとする。 位置 配列 0 (ア) 1 (イ) 2 (ウ) 3 (エ) 4 (オ) 【問2】 相違なるn個のデータが昇順に整列された表がある。この表を1ブロックm個に分割し、各ブロックの最後尾のデータだけ線形検索することによって、目的のデータを探し出す。 次に当該ブロック内を線形検索して目的のデータを探し出す。 このときの平均探索(比較)回数は(ア)~(エ)のうちどれか。 ここでm<nとし、目的のデータは必ず表の中に存在するものとする。 (ア) (イ) (ウ) (エ) n n n m n ─ ─ m + ─ ─+─ m 2m m 2 2m 【問3】 次の手順はシェルソートによる整列を示している。 データ列”7,2,8,3,1,9,4,5,6”を手順(1)~(4)に従って整列すると手順(3)を何回繰り返して完了するか。 ここで、〔〕は小数点以下を切り捨てる。 <手順> (1)〔データ数÷3〕→Hとする。 (2)データ列を互いにH要素分だけ離れた要素の集まりからなる部分列とし、それぞれの部分列を挿入方を用いて整列する。 (3)〔H÷3〕→Hとする (4)Hが0であればデータ列の整列は完了し、0でなければ(2)に戻る。 以上になります。
- ベストアンサー
- その他([技術者向] コンピューター)
- アルゴリズムによる整列方法について
以下の問題を授業外課題として出されましたがわかりません。身近に分かる人物もいません。 先生も答えてくれません。 解答お待ちしております。 1.以下の文章の空欄を埋めよ.但し,((14)),((15)) については,選択肢から最も適切なものを選び,記号で答えよ.加えて,解答の過程を詳しく述べよ。 高速な整列として以下のアルゴリズムによる方法を考える.以下では,整数データを昇順に配列するも のとする. 前段階として,データを半々に二つのグループ I と II に分割し,それぞれを独立に整列する. while (両グループに要素が残っている) do if (グループ I の最小要素 < グループ II の最小要素) then グループ I の最小要素を出力場所に移し,グループ I からは削除する else グループ II の最小要素を出力場所に移し,グループ II からは削除する endif done while (グループ I に要素が残っている) do グループ I の要素を出力場所に移し,グループ I からは削除する done while (グループ II に要素が残っている) do グループ II の要素を出力場所に移し,グループ II からは削除する done この整列に要する計算量 T(n) を求める.但し,n は整列するデータの量である.前段階の整列では,半分のデータ量の整列を 2 回行うので ((1)) だけの計算を要する.次に,3 個の while 反復のいずれについても, 「反復を 1 回行うごとに要素が一つだけ出力場所に移動する」 ことから,3 個を合計すると反復の中身は正確に ((2)) 回実行されることが分かる.1 回の実行に a だけの時間がかかるものとすれば,全体で ((3)) となる.従って次の関係式が成り立つ. T(n) = ((4)) 簡単のため,n = 2^p であるとすると, T(n) = ((5))×T(2^((6)) ) + ((7)) = ((8)) × T(2^((9)) ) + 2 × ((7)) ・ ・ ・ = ((10)) × T(2^0) + ((11)) T(2^0) = ((12)) なので,T(n) を a と n のみを用いて表すと, T(n) = ((13)) であり,これは, ((14)) に比例し,計算量のオーダーは ((15)) といえる. ((14)),((15)) の選択肢 a. n b. n^2 c. 2^n d. n log n e. log n f. いわゆる「指数オーダー」であり,アルゴリズムとして全く実用に耐えない g. いわゆる「バカソート」と同じであり,n がごく小さい場合を除いて実用には適さない h. 経験上最速とされるソート法には及ばないが,それほど大きくない n に対しては実用に耐える i. 経験上最速とされるソート法と同じであり,十分大きい n に対しても実用に耐える
- 締切済み
- 数学・算数
- オートシェイブの図形の調整で配置/整列ができない
ワード2002です 表の挿入で4つの枠をつくりました 1つの枠内で信号機を表現するためオートシェイブで 円を3個描きましたが不揃いなので図形の調整で 配置/整列を選択してもメニューが灰色のままで 選択できませんなぜか判りません 枠をつくらないですると配置/整列が選択できます 初心者で質問も上手に表現できませんがアドバイス お願いします
- 締切済み
- その他(ソフトウェア)
- アルゴリズムお願いします
必修科目「数学」、選択必修科目「歴史」と選択必修科目「地理」の3科目がある。ある2人の学生に対して、「二人とも進級か」「一人が留年」あるいは「二人とも留年」を出力する問題を考える。ただし、進級条件は「必修科目に合格し、かつ二科目の選択必修科目の少なくとも1科目に合格していること」とし、全学生が3科目とも履修しているものとする。 問題1 この問題に対するアルゴリズムのステップをかけ/ GP1 (S0)Aが数学に合格かをみる。合格であれば(S1に進む)不合格の場合、留年となる (S1)Aが歴史に合格しているかどうかを見る。合格であれば進級とする。不合格であれば(S2に進む) (S2)Aが地理に合格しているかどうかを見る。合格であれば進級とし、不合格であれば留年とする。 (S3)Bが数学に合格しているかどうかを見る。合格であれば(S4)に進む。 (S4)Bが地理に合格しているかどうかを見る。合格であれば進級とし、不合格であれば留年とする。 問題2 その時、最大時間計算量、領域計算量をそれぞれ求めよ。
- ベストアンサー
- ネットワーク
- アルゴリズム 教えてください
必修科目「数学」、選択必修科目「歴史」と選択必修科目「地理」の3科目がある。ある2人の学生に対して「二人とも進級」か「一人が留年」あるいは「二人とも留年」を出力する問題を考える。ただし、進級条件は「必修科目に合格し、かつ2科目の選択必修科目の少なくとも1科目に合格していること」とし、全学生が3科目とも履修しているものとする。 実行結果 ある一人の学生が進級する科目取得パターンを全て書いてください (例) 数学「合格」歴史「不合格」地理「合格」 実行結果 この問題に対するアルゴリズム(手順)のステップを書いてください 実行結果 そのときの最大時間計算量(1点)、領域計算量(1点)をそれぞれ求めよ。 すべて教えていただきたいです。
- 締切済み
- Java