締切済み

ソートの問題

2008/10/06 17:47

ソートの問題なんですが、選択ソートの交換回数はどのような場合も等しくなるんでしょうか??また、バブルソートと挿入ソートの交換回数は等しくなるのか教えてください＞＜

kametatu
お礼率20% (2/10)

C・C++・C#
回答数1
ありがとう数0

みんなの回答 （1）
専門家の回答

みんなの回答

asuncion
ベストアンサー率33% (2127/6289)

2008/10/06 18:02 回答No.1

各々のソートアルゴリズムを実装するコードを書いて、「ご自分で」交換回数を数えてみるほうが、人に聞くよりも知識として定着しやすいと思います。

関連するQ&A

ソートアルゴリズム（選択法とバブルソート）の交換回数

バブルソートと選択法について、交換回数がわかりません。比較回数については、ネットで検索したり、本に載っているので分かりやすいのですが、交換回数があまり載っていなく…。選択法の交換回数の最大値は、n-1でしょうか？バブルソートの交換回数の最大値は、nでしょうか？交換回数については、選択法のほうがバブルソートより少なくてすむそうですが、上の答えでいいのかわかりません。どなたか教えてください。お願いしますm(_ _)m
バブルソートとセレクションソートの交換回数について

はじめまして。自学でCを学んでいるものです。いきなりですが、タイトルの通り、バブルソートとセレクションソート（直選択ソート）の交換回数が同じになるということは分かるのですが、その理由が分かりません。何となくわかっているのですが、ｎや数式を用いて論理的に説明しろと言われると、お手上げです。自分の理解のためにもこの点はしっかりと押さえておきたいと思っています。何卒よろしくお願いします。
バブル・ソート、クイック・ソート

N個（N=4,5,6）のデータが全て等しいデータ列（例えばN個の数字全部が1のとき）をバブルソートで並び替えたとき、データの交換回数は何回か。また、同じデータ列をクイックソートで並び替えたときはどうか。という問題があるのですが、どう比較するのかがわかりません。詳しい方、説明よろしくお願いします。
挿入ソートとバブルソート

挿入ソートとバブルソートについて教えてください。どのようなアルゴリズムでソートされるのでしょうか？
modified bubble sort

　ソーティングについて教えてください．　ソーティングの手法に，バブルソートというものがあります(隣接するふたつを入れ替える)．このソーティングでは，最大交換回数は要素数が n のとき， n(n-1)/2 となります．　隣接する要素の交換に加え，先頭と最後の要素の入れ替えも可能だとすると(イメージとしては，サイクリックなバブルソートです)，最大交換回数は n^2/4 となるそうです．　この n^2/4 になる，という理由が分かりません(普通のバブルソートが n(n-1)/2 になるのは理解できます)．どなたかご教授頂ければと思います．
単純挿入ソートについて

単純挿入ソートの『選択』、『交換』、『挿入』の回数を出力せよ。という課題が出されたのですが意味がよくわかりません。ちなみに課題前に次のような説明をされました。『選択』は交換と挿入を行うため、キー値等の比較を行う判定処理『交換』は選択の結果、2つのキー値の並び替え処理『挿入』は選択の結果、キー値を決められた並び順の位置に格納する処理また、『選択』を『比較』、『交換』と『挿入』を合わせて『交換』と言う事もある。作ったプログラムはこれです。かなり違う気がするので指摘よろしくお願いします。 void insertion(int a[], int n) /* a[]:ソート対象データが格納されている配列 n:データの個数 */ { int i,j; int tmp; int count[3]; /* 配列番号選択:0 交換:1 挿入:2 */ for(i=1;i<n;i++) { tmp=a[i]; count[1]++; /* 交換カウント */ for(j=i;(j>0)&&(a[j-1]>tmp);j--,count[0]+=2) /* 選択カウント */ { a[j]=a[j-1]; count[1]++; /* 交換カウント */ } if(j > 0) /* 選択カウント */ count[0]+=2; else count[0]++; a[j]=tmp; count[2]++; /* 挿入カウント */ } printf("選択の回数 : %4d\n", count[0]); printf("交換の回数 : %4d\n", count[1]); printf("挿入の回数 : %4d\n\n", count[2]); } テストデータ 60 57 54 51 48 45 42 39 36 33 30 27 24 21 18 15 12 9 6 3 実行結果選択の回数 : 399 交換の回数 : 209 挿入の回数 : 19
C言語、ソートの効率を考える問題について

繰り返しソートとバブルソート、改良バブルソートの中でどれが一番効率的であるかを理論的な比較回数やプログラムの量、使用するメモリの量から考えたいんですけどわかりません。教えてください。
アルゴリズムの問題なのですが、マージソートとクイックソートについて教え

アルゴリズムの問題なのですが、マージソートとクイックソートについて教えてください。数列の(21 99 38 22 15 6)をマージソートで並び変えて、クイックソートでも並び変えたいのです。マージソートで並び変えた手順は (21 99 38 22 15 6) (下矢印) (21 99 38)(22 15 6) (下矢印) (21 99)(38)(22 15)(6) (下矢印) (21)(99)(38)(22)(15)(6) (下矢印) (21 99)(38)(15 22)(6) (下矢印) (21 38 99)(6 15 22) (下矢印) (6 15 21 22 38 99) となりました。この時、分割回数と統合回数がともに5なのですが、どう見たら5回なのでしょうか。分割回数は3で統合回数も3ではないのでしょうか？クイックソートの方なのですが、回答は (21 99 38 22 15 6) (下矢印) (15 6)(21)(99 38 22) (下矢印) (6)(15)(21)(22 38)(99) (15と38にした場合) (下矢印) (6)(15)(21)(22)(38)(99) となっていて、最も効率のよいピボットを選択した場合分割回数は3となっています。私がやってみたところ (21 99 38 22 15 6) (下矢印) (15 6)(21)(99 38 22) (下矢印) (6)(15)(21)(22)(38)(99)　　(15と38を選んだ) これではいけないのでしょうか。長くなりましたが、よろしくお願いします。
バブルソートとクイックソート

まだソートについて勉強し始めたばかりですがバブルソートは対象の総数が増えるとそれに伴い比較回数は増加するのに対しクイックソートはそれほど増加しないのはなぜでしょうか？？検索してみてもプログラムが書いてあってよくわからないので... 根本的なところなのでしょうがどなたか教えてください!
バブルソートの交換回数、連結（リンク）リストの短所

バブルソートの交換回数を表す一般的な式（nを用いた式）が分かりません。具体的には n個のメンバーの場合1ラウンドあたりn/2回の交換なので全ラウンドでの交換は[(n/2)*{(n-1)/2}]/2=n*(n-1)/8回となるらしいのです。でも例えば例題で「96 23 87 8 76」というn=5の数字群をバブルソートで並び替えるには、上の式だと並び替える回数は2.5回になってしまいます。小数が出るのはおかしいと思うのですが・・・この場合交換回数は地道に数えるしかないのでしょうか。ちなみに比較回数はn(n-1)/2なので10と出せました。あと連結（リンク）リストの長所は検索できたのですが短所についての記述が見つかりません。短所はあるのでしょうか、あるならどのような内容なのでしょうか。一方でもいいので宜しくお願いします。
単純挿入ソート法の要素の比較回数についての問題

単純挿入ソート法の要素の比較回数、移動回数についての問題『単純挿入ソート法は、シャトルソート法とも呼ばれ、挿入とシフトを用いるソートである。下図（添付図）はこのソート法の１ステップを示している。配列a[0],…,a[n-1]があって、a[i]より前の部分がソートされている。ここで、a[i]の値をwとする。 a[0],…,a[i-1]の部分で、w が入るべき位置を探す。この位置をj とする。配列の範囲 a[j],…,a[j-1]をa[j+1],…,a[i] ヘシフトする。最後に、wをa[j]に格納する。このような操作を、最後まで繰り返す。以下の問に答えよ。問(1)～(3) 省略問(4)単純挿入ソート法で要素の比較回数のオーダーを答えなさい。ただし、配列の要素数を n とする。問(5)単純挿入ソート法で要素の移動回数のオーダーを答えなさい。ただし、配列の要素数を n とする。』問(1)～(3)は単純挿入ソート法で配列を昇順にソートするC言語で記述されたプログラムに関する問題なのですがそちらは解けました。問(4)は比較回数のオーダーを S とすると、最悪の場合 n(n-1)/2 回比較を行う必要があるので、S=n(n-1)/2 問(5)は移動回数のオーダーを T とすると、最悪の場合 n(n-1)/2 回移動を行う必要があるので、T=n(n-1)/2 と考えているのですが自信がありません。そもそもここで問われているオーダーとは回数のことをいってるのか、そうではないのかが分かりません。どなたか説明していただけますと大変助かります。解答以外にもこの問題に関連することに対してのアドバイスなどがありましたら答えてくださると嬉しいです。時間がなくて少し焦っています。どうか何卒よろしくお願いします。
バブルソートの実行時間について

バブルソートで降順、ランダム順に並んでいるデータを読み込ませて昇順に並び替える実行時間について質問です。バブルソートにおける計算時間は、データ数が多いほど、並び替える回数が多いほど長くなるはずですが、実際に実行したところ、並び替える回数が多いはずの降順のほうがランダム順よりも早くなりました。なぜこのようになるのですか？よろしくお願いします。
挿入ソートの性能評価

挿入ソートの要素比較回数と要素交換回数を数えるプログラムを作りたいのですがうまくいきません。。。学校で出された演習課題ですので、解答そのものをいただくよりは、プログラム作成のヒントになるような回答をしていただきたいと思っています。どうかよろしくお願いします。
比較回数が少なくなるソート

大量にある画像に人間が優劣を判定し、その結果をソートしたいです。（順位を付けたい）画像はすでにデジタルデータ化されてパソコンの中にあります。二つの画像を人間に見せて判断を求める事を繰り返すプログラムを作成しようと思うのですが、人間が行う操作（比較の判断）をなるべく少なくする為には、どのようなソートのアルゴリズムを選択したら良いでしょうか？ソートのアルゴリズムの説明などを読むと、例えば、「バブルソート」及び「選択ソート」ではｎ(ｎ－１)／２の比較が必要になるそうですが、この比較の回数が最も少ない方法を探しています。また、例えばA,B,Cの比較に置いて、 A＞B、B＞Cの比較後にはAとCは比較せずともA＞Cの関係が成り立つのですが、こういった事も考慮した上での比較回数の最も少ないソートの方法が知りたいです。以上、ご指導のほど、よろしくお願い申し上げます。
挿入ソートとマージソート

挿入ソートとマージソートの問題を解いているのですが、途中で行き詰ってしまいました。（問題文）サイズnの入力に対して、挿入ソートの実行には8n~2ステップかかり、マージソートの実行には64nlnnステップかかる。挿入ソートがマージソートに勝るnの値を求めよ。補足：ln=eを底とするlog （挿入ソートがマージソートに勝る＝挿入ソートがマージソートより実行時間が早い） 8n~2 <= 64nlnn 8lnn=n e~n=n~8 こういう感じで自分なりに考えてみたのですが、nの値をどのように出して良いのかわからず困っています。どなたかご教授いただける方いましたらよろしくお願いします。
ソートプログラムで

１．２つの配列a、bをマージする場合、比較回数が最大となる必要十分条件、最小となる必要十分条件２．マージソートプログラムと選択ソートプログラムの比較回数について、要素数をｎとしたときに、比較回数をｎで表すにはどうしたらよいですか？初心者なので全然わかりません。教えてください。
ソートに関する質問です

C言語でのプログラム作成の課題が解けなくて困っています。バブルソートを使って、1000000個の整数データを昇順に並べ替えるプログラムを作成するというものです。自分なりに作成したプログラムは、mallocでデータを格納する動的領域を確保して、後はシンプルにバブルソートの処理を行っています。データ数が5，6万程度なら正常な動作が確認できるのですが、それより大量のデータ数だと、処理に時間が掛かりすぎるせいか、もしくは処理しきれずに動かなくなってしまったのか分かりませんが、プログラムの処理がいつまでたっても終わりません。おそらくバブルソートの2重ループのあたりで、膨大な処理になってしまうのだと思うのですが、この問題についての改善策をどなたかご教授いただけませんでしょうか。
ソートプログラム

基本的なソートプログラムを何個か書いています。（直接選択法、バブル、クイックetc・・）１０００個の値を乱数で発生させ、１００回、２００回、３００回、・・・と入れ替えを行った値を出力したいのですが、どうしたらよいか分かりません。どなたか教えてください。
ソート（データの並べ替え）の逆概念はシャッフル？

ソートは、データの集合を一定の規則に従って並べること。バブルソート、シェーカーソート、コムソート、選択ソート、挿入ソート、シェルソート、ヒープソート、マージソート、クイックソート、バケットソート、基数ソート、逆写像ソート、ボゴソート、奇偶転置ソート、シェアソートなどがあるそうです。ではその逆概念の、データの集合を一定の規則に従ってバラバラにすることってなんといいますか? トランプ（カードマジック）でよく見かけるシャッフルのことでしょうか？ディールシャッフル、ヒンズーシャッフル、オーバーハンドシャッフル、リフルシャッフル、ファローシャッフルなどがあるそうです。それらを数学的に扱ったものってありますか？
ソート（乱数・比較・交換・時間）

ソート（コームソート）について色々と実験をして確めてみようと思っています。乱数を５００、１０００、１５００個ずつで、山型、逆ソートなどでで発生させて、さらに比較回数・交換回数・時間を計りたいのですが、プログラムが出来るようでなかなかうまくいきません。どのようにつくればいいのでしょうか？また、参考になるホームページがあれば教えていただければありがたいです。

ソートの問題

みんなの回答

関連するQ&A

ソートアルゴリズム（選択法とバブルソート）の交換回数

バブルソートとセレクションソートの交換回数について

バブル・ソート、クイック・ソート

挿入ソートとバブルソート

modified bubble sort

単純挿入ソートについて

C言語、ソートの効率を考える問題について

アルゴリズムの問題なのですが、マージソートとクイックソートについて教え

バブルソートとクイックソート

バブルソートの交換回数、連結（リンク）リストの短所

単純挿入ソート法の要素の比較回数についての問題

バブルソートの実行時間について

挿入ソートの性能評価

比較回数が少なくなるソート

挿入ソートとマージソート

ソートプログラムで

ソートに関する質問です

ソートプログラム

ソート（データの並べ替え）の逆概念はシャッフル？

ソート（乱数・比較・交換・時間）

注目のQ&A

カテゴリ
一覧

専門家に質問してみよう
専門家登録

あなたにピッタリな商品が見つかる！ OKWAVE セレクト

ソートの問題

みんなの回答

関連するQ&A

ソートアルゴリズム（選択法とバブルソート）の交換回数

バブルソートとセレクションソートの交換回数について

バブル・ソート、クイック・ソート

挿入ソートとバブルソート

modified bubble sort

単純挿入ソートについて

C言語、ソートの効率を考える問題について

アルゴリズムの問題なのですが、マージソートとクイックソートについて教え

バブルソートとクイックソート

バブルソートの交換回数、連結（リンク）リストの短所

単純挿入ソート法の要素の比較回数についての問題

バブルソートの実行時間について

挿入ソートの性能評価

比較回数が少なくなるソート

挿入ソートとマージソート

ソートプログラムで

ソートに関する質問です

ソートプログラム

ソート（データの並べ替え）の逆概念はシャッフル？

ソート（乱数・比較・交換・時間）

注目のQ&A

カテゴリ 一覧

専門家に質問してみよう 専門家登録

あなたにピッタリな商品が見つかる！ OKWAVE セレクト

カテゴリ
一覧

専門家に質問してみよう
専門家登録