- 締切済み
ソートプログラムで
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- BLUEPIXY
- ベストアンサー率50% (3003/5914)
１． 例えば、配列ａの要素数がｎで配列ｂの要素数がｍだとして ｍ＞ｎでａの要素の最大値がｂの要素の最小値より小さいなら比較回数はｎ回で良くてこの時が最小になるんじゃないかと思います。 逆に最大になる時とは、ａとｂの要素数が同じでデータの大きさの順番が互い違いになるような場合じゃないかと思います。 ２． 選択ソートにおける最悪の場合の比較回数については、すでに、以前回答したことがあります。 マージソートの最悪の場合の比較回数については、１．から簡単に求めることができると思います。 合ってるかどうかは、実際のプログラムを書いて動かしてみるといいと思います。
関連するQ&A
- 単純挿入ソート法の要素の比較回数についての問題
単純挿入ソート法の要素の比較回数、移動回数についての問題 『単純挿入ソート法は、シャトルソート法とも呼ばれ、挿入とシフトを用いるソートである。 下図（添付図）はこのソート法の１ステップを示している。 配列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 と考えているのですが自信がありません。 そもそもここで問われているオーダーとは回数のことをいってるのか、そうではないのかが分かりません。 どなたか説明していただけますと大変助かります。解答以外にもこの問題に関連することに対してのアドバイスなどがありましたら答えてくださると嬉しいです。 時間がなくて少し焦っています。どうか何卒よろしくお願いします。
- 締切済み
- C・C++・C#
- modified bubble sort
ソーティングについて教えてください． ソーティングの手法に，バブルソートというものがあります(隣接するふたつを入れ替える)．このソーティングでは，最大交換回数は要素数が n のとき， n(n-1)/2 となります． 隣接する要素の交換に加え，先頭と最後の要素の入れ替えも可能だとすると(イメージとしては，サイクリックなバブルソートです)，最大交換回数は n^2/4 となるそうです． この n^2/4 になる，という理由が分かりません(普通のバブルソートが n(n-1)/2 になるのは理解できます)．どなたかご教授頂ければと思います．
- 締切済み
- 数学・算数
- ソートアルゴリズム（選択法とバブルソート）の交換回数
バブルソートと選択法について、交換回数がわかりません。 比較回数については、ネットで検索したり、本に載っているので分かりやすいのですが、交換回数があまり載っていなく…。 選択法の交換回数の最大値は、n-1でしょうか？ バブルソートの交換回数の最大値は、nでしょうか？ 交換回数については、選択法のほうがバブルソートより少なくてすむそうですが、上の答えでいいのかわかりません。 どなたか教えてください。お願いしますm(_ _)m
- 締切済み
- その他([技術者向] コンピューター)
- マージソートについて
マージソートの要素の比較と交換回数を計測するプログラムを作っているのですが、マージのどの段階が交換処理になるのかが分からず困っています。 マージ処理の実行回数をカウントする配列ｓを設けて処理をカウントする場合、以下のプログラムだとどのタイミングでカウントすればよいでしょうか？ ちなみに配列aは初めに値を割り振った配列で、配列bは別途で用意した作業用配列です。 最後のfor文やif文付近で配列の値を変化させて計測してみたのですが、計算量に合った動きをしてくれませんorz void merge_sort(int a[], int low, int high){ int mid, i, j, k; if(low >= high) return; mid = (low + high)/2; merge_sort(a, low, mid); merge_sort(a, mid+1, high); for(i = low; i <= mid; i++) b[i] = a[i]; for(i = mid+1, j=high; i <= high; i++, j--) b[i] = a[j]; i = low; j = high; for(k = low; k <= high; k++){ if(b[i] <= b[j]){ a[k] = b [i++]; } else{ a[k] = b[j--]; } } }
- ベストアンサー
- C・C++・C#
- Javaのプログラムが完成出来ません・・・
この前、大学からこんな課題が出されました。 以下の条件が含まれてるシェルソートのプログラムを作成せよ。 条件。 ・ソート済み部分に新しい値を挿入するための空き場所を作るメソッドを入れること。 ・配列の逆順数を計算するメソッドを入れる。 ・今の歩幅より一段階小さい歩幅を計算するメソッドを入れる。 ・配列の大きさに一番合った歩幅を計算するメソッドを入れる。 ・歩幅hの挿入ソートを行うメソッドを入れる。 ・シェルソートを行うメソッドを入れる。 ・mainメソッドを完成させ、ソート過程を表示しながらシェルソートを実行するようにする。 ・作成したプログラムが正しく選択ソートを実行していることが分かる実行結果を示すこと。 ・値は、 a[0]=0, a[1]=30, a[2]=20,a[3]=10 一応プログラムは、 class ShellSort{ static int compare = 0; static int copy = 0; static void showArray(int a[], int N){ //2-0:逆順数と共に配列の内容を表示するメソッド //動作:N個の要素を持つ配列aの要素を全て画面に表示する //} static void initArray(int a[], int N){ //2-0:配列にランダムな値を代入するメソッド //動作:N個の要素を持つ配列aに対し、1～Nまでの範囲の数をランダムに入れる //ただし、a[0]には常に0を入れること。 } static int shiftLargerElements(int a[], int v, int i){ //2-0:ソート済み部分に新しい値を挿入するための空き場所を // 作るメソッド //動作:配列aに対し、a[i]より手前にあるvより大きい要素を後ろ //に1つずつずらしてvを挿入するための空き場所を作る。最後に、 //できた空き場所の添え字を戻り値として返す。 //空き場所を作るまでに行った比較回数を変数compareに加算 //空き場所を作るまでに行ったコピー回数を変数copyに加算 int space = 0; int j; j = i; while((compare++ >= 0) && (a[j-1] > v)){ a[j] = a[j-1]; copy++; j--; } space = j; return space; } static int shiftLargerElements(int a[], int v, int i, int h) { //2-1:ソート済み部分に新しい値を挿入するための空き場所を // 作るメソッド //動作:配列aに対し、a[i]より手前にある要素 //a[i-h],a[i-2h],a[i-3h],...のうち、vより大きい各要素を後ろに //hだけ移動させてvを挿入するための空き場所を作る。 //最後に、できた空き場所の添え字を戻り値として返す。 //空き場所を作るまでに行った比較回数を変数compareに加算 //空き場所を作るまでに行ったコピー回数を変数copyに加算 int space = 0; return space; } 現在はここまでしか作成出来てません。 それ以降でつまづいています。 分かる人がいましたら、是非教えて下さい。
- 締切済み
- Java
- ソートのプログラム
Fortranなのですが、実数のソートプログラムを作る必要があります。 x(1),...x(20)ぐらいの配列に実数が入っていて小さい順番に並べるというものです。ソートプログラムは何種類かあると思います。数千回ぐらいやるので速いほうがいいです。 ソートプログラムのソースなどを公開しているサイトがないでしょうか。検索しても発見できませんでした。やっぱりサブルーチン集を買うなどするのがよいでしょうか。自分で作ってもよいですが、ネット上に公開されているようなものを収集して作ってみたいと思っています。 よろしくお願いします。
- 締切済み
- その他（プログラミング・開発）
- マージソートの計算量について-O(n*logn)
マージソートの計算量はO(n*logn)ですが、なぜそうなのかが理解出来ません。要素数が2, 4, 8, 16, 32, 64...と増加すると二分割するのにかかる時間は1, 2, 3, 4, 5, 6..となり、n=2^x, x=lognとなるところまでは理解出来ました。しかし更にnをかける必要があるのはどうしてでしょうか。要素数が１になるまで分割した後に、小さい順番に比較しながら統合して行く作業があり、これにも当然ランニングタイムがかかるのはわかりますがなぜこの要素の比較コスト？が*nなのでしょうか。 またウェブで調べると、他にもT(n)=2T(2/n)+O(n)という別の説明もあり、こちらも理解出来ません。この説明は上の説明とはまた別の角度から説明しているものなのでしょうか。わかる人がいたら教えて下さい。
- ベストアンサー
- C・C++・C#
- 比較回数が少なくなるソート
大量にある画像に人間が優劣を判定し、その結果をソートしたいです。（順位を付けたい） 画像はすでにデジタルデータ化されてパソコンの中にあります。 二つの画像を人間に見せて判断を求める事を繰り返すプログラムを作成しようと思うのですが、人間が行う操作（比較の判断）をなるべく少なくする為には、どのようなソートのアルゴリズムを選択したら良いでしょうか？ ソートのアルゴリズムの説明などを読むと、例えば、「バブルソート」及び「選択ソート」ではｎ(ｎ－１)／２の比較が必要になるそうですが、この比較の回数が最も少ない方法を探しています。 また、例えばA,B,Cの比較に置いて、 A＞B、B＞Cの比較後にはAとCは比較せずともA＞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を選んだ) これではいけないのでしょうか。 長くなりましたが、よろしくお願いします。
- ベストアンサー
- その他([技術者向] コンピューター)
- C♯の配列について
Ｃ♯でプログラムを作っているのですが、配列の要素数の最大値と最小値の求め方がわかりません。配列の値の最大値の求め方は調べれば出てくるのですが、要素数の最大値等は調べてもわかりませんでした。 例えば下記のような配列があった場合 int[,,] a =new int[100,100,100] a[2,3,6]=1 a[4,5,9]=1 a[13,46,79]=1 a[8,15,45]=1 a[1,33,68]=1 それぞれの要素数の最小値１、３、６、最大値１３、４６、７９は どのようにプログラムで求めればいいのでしょうか？ よろしくお願いします。
- 締切済み
- その他（プログラミング・開発）
