- ベストアンサー
バブルソートとセレクションソートの交換回数について
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
> 比較回数はバブルソートと同様だが、要素の数が同じなら交換回数は常に同じという、安定性の高いアルゴリズムである。 これは、「バブルソートと選択ソートで交換回数は同じ」という意味ではありません。 「選択ソートでは、要素の数が同じなら、どんな入力データでも交換回数は同じ」という意味です。 たとえば、10要素の選択ソートなら、 「順序的に1番目にくるべき要素を、1番目と交換」 「順序的に2番目にくるべき要素を、2番目と交換」 … 「順序的に9番目にくるべき要素を、9番目と交換」 という流れになり、 どんな入力データであっても、10要素のソートなら交換回数は必ず9回になります。 一方、バブルソートの場合は、入力データの並びによって、交換回数が変わってきます。
その他の回答 (2)
- mtaka2
- ベストアンサー率73% (867/1179)
入力がある特定の並びについて「バブルソートと選択ソートの交換回数が同じ」であることはありえますが、 総じて見ると「バブルソートと選択ソートの交換回数の比較」では、基本的に「バブルソートの方が交換回数が多い」ことになります。 アルゴリズムの優劣を論じる状況においては「バブルソートと選択ソートの交換回数が同じ」などと言うことはありません。 参考: http://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88 > 多くのC言語のサイトを見てみると、交換回数が同じとしている 具体的に、どのサイトにそういう記述があるのか教えてくれませんか?
- mtaka2
- ベストアンサー率73% (867/1179)
バブルソートと選択ソートでは、交換回数は同じではありません。選択ソートの方が少なくなります。 バブルソートでは、二重ループの中で必要に応じて交換が行われますので、交換回数はO(n^2)です。 選択ソートでは、二重ループの中は「最小要素の探索」=「比較」のみで、交換はその外の一重ループレベルで行われます。交換回数はO(n)です。 一方、比較回数は、どちらも同じになります。
補足
回答ありがとうございます。このソートというものは、重複はなしです。 多くのC言語のサイトを見てみると、交換回数が同じとしているのは、また違った条件からなのでしょうか？ 転倒数について考えるとその理由が出てくる、という記述のあるサイトがありましたが、それは関係あるでしょうか？
関連するQ&A
- ソートアルゴリズム（選択法とバブルソート）の交換回数
バブルソートと選択法について、交換回数がわかりません。 比較回数については、ネットで検索したり、本に載っているので分かりやすいのですが、交換回数があまり載っていなく…。 選択法の交換回数の最大値は、n-1でしょうか？ バブルソートの交換回数の最大値は、nでしょうか？ 交換回数については、選択法のほうがバブルソートより少なくてすむそうですが、上の答えでいいのかわかりません。 どなたか教えてください。お願いしますm(_ _)m
- 締切済み
- その他([技術者向] コンピューター)
- modified bubble sort
ソーティングについて教えてください． ソーティングの手法に，バブルソートというものがあります(隣接するふたつを入れ替える)．このソーティングでは，最大交換回数は要素数が n のとき， n(n-1)/2 となります． 隣接する要素の交換に加え，先頭と最後の要素の入れ替えも可能だとすると(イメージとしては，サイクリックなバブルソートです)，最大交換回数は n^2/4 となるそうです． この n^2/4 になる，という理由が分かりません(普通のバブルソートが n(n-1)/2 になるのは理解できます)．どなたかご教授頂ければと思います．
- 締切済み
- 数学・算数
- バブルソートの交換回数、連結（リンク）リストの短所
バブルソートの交換回数を表す一般的な式（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と出せました。 あと連結（リンク）リストの長所は検索できたのですが短所についての記述が見つかりません。 短所はあるのでしょうか、あるならどのような内容なのでしょうか。 一方でもいいので宜しくお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- バブル・ソート、クイック・ソート
N個（N=4,5,6）のデータが全て等しいデータ列（例えばN個の数字全部が1のとき）をバブルソートで並び替えたとき、データの交換回数は何回か。また、同じデータ列をクイックソートで並び替えたときはどうか。 という問題があるのですが、どう比較するのかがわかりません。詳しい方、説明よろしくお願いします。
- 締切済み
- C・C++・C#
- 比較回数が少なくなるソート
大量にある画像に人間が優劣を判定し、その結果をソートしたいです。（順位を付けたい） 画像はすでにデジタルデータ化されてパソコンの中にあります。 二つの画像を人間に見せて判断を求める事を繰り返すプログラムを作成しようと思うのですが、人間が行う操作（比較の判断）をなるべく少なくする為には、どのようなソートのアルゴリズムを選択したら良いでしょうか？ ソートのアルゴリズムの説明などを読むと、例えば、「バブルソート」及び「選択ソート」ではｎ(ｎ－１)／２の比較が必要になるそうですが、この比較の回数が最も少ない方法を探しています。 また、例えばA,B,Cの比較に置いて、 A＞B、B＞Cの比較後にはAとCは比較せずともA＞Cの関係が成り立つのですが、こういった事も考慮した上での比較回数の最も少ないソートの方法が知りたいです。 以上、ご指導のほど、よろしくお願い申し上げます。
- ベストアンサー
- その他（プログラミング・開発）
- 比較回数と交換回数表示について
クイックソートとバブルソートの比較回数と交換回数を確認するため以下のようなプログラムを作成しました。 #include <stdio.h> #define SIZE 32 short bubble_sort(short s[],int x); short quick_sort(short s[],int y,int z); void show(short s[],int n); short bubble_sort(short s[],int x){ //バブルソート int i,j,count,sum; short tmp; count=0; sum=0; for(i=0; i<SIZE; i++){ for(j=i+1; j<SIZE; j++){ count++; if(s[i] > s[j]){ tmp=s[i]; s[i]=s[j]; s[j]=tmp; sum++; } } } show(s,SIZE); printf("\n比較回数:%d回\n交換回数:%d回\n",count,sum); } short quick_sort(short s[],int left,int right){ //クイックソート int i, j,tmp,count,sum; int point; i = left; j = right; point = s[(left + right) / 2]; count=0; sum=0; while (right!=1) { count++; while (s[i] < point) i++; count++; while (point < s[j]) j--; if (i >= j) break; tmp=s[i]; s[i]=s[j]; s[j]=tmp; i++; j--; sum++; } show(s,SIZE); printf("\n比較回数:%d回\n交換回数:%d回\n",count,sum); if (left < i - 1) quick_sort(s, left, i - 1); if (j + 1 < right) quick_sort(s, j + 1, right); } void show(short s[], int n) { int i; for (i = 0; i < n ; i++){ printf("%d ", s[i]); } printf("\n"); } int main(void){ short s[SIZE] ={25,29,1,32,14,22,26,3,15,27,5,7,24,12,31,23,6,20,10,8,18,16,11,30,13,2,4,21,17,19,9,28}; printf("ソート前:\n"); show(s,SIZE); printf("バブルソート後:\n"); bubble_sort(s,SIZE); printf("\n"); short t[SIZE] ={25,29,1,32,14,22,26,3,15,27,5,7,24,12,31,23,6,20,10,8,18,16,11,30,13,2,4,21,17,19,9,28}; printf("ソート前:\n"); show(t, SIZE); printf("ソート中:\n"); quick_sort(t,0,SIZE-1); printf("クイックソート後:\n"); show(t,SIZE); } これを動かして頂ければ分かるとは思いますが、バブルソートの時のような結果（途中経過なしで最終結果と比較回数と交換回数の表示）を クイックソートでも出したいのですが、うまく出せずに困っています。 どのようにすれば良いのかご指導いただけませんでしょうか？また、実行環境が会社にしかないので、 できれば結果も頂けるとありがたいです。失礼ですみませんがよろしくお願い致します。
- 締切済み
- C・C++・C#
- バブルソート
int a[] = {8,45,15,90,62,73,22}をバブルソートを使用して、降順で並べ替える。 以下の説明では、配列の要素数（ここでは７）をＮとしている。 (1) a[N-1] と a[N-2] を比較し、a[N-1] が a[N-2] より大きい場合は、a[N-1] と a[N-2] を入れ替える。 同様に a[ j] が a[ j-1] より大きければ、a[ j] と a[ j-1] を入れ替える。 この操作を、j=N-1からiまで繰り返す。ただし、iは(1)の処理回数を表す値である。(初回を0とする） (2) (1)を i=0 から N-2 まで繰り返す。 (3) 以下の<実行例>を参考に、配列ａのようその各値を標準出力する。 <実行例> 90 73 62 45 22 15 8 という問題なのですが、どうやってもうまく並び替えられません。 a[N-1] の処理はいらないのではないのですか？ どのようにプログラムを書いたらいいのか教えて下さい。 あつかましいですが、できたら解説付きでお願いします。
- ベストアンサー
- Java
- クイックソートの交換回数
クイックソートを行うプログラムを書いています。 これを、比較回数と交換回数を表示できるように改良したいのですが、うまくいきません。カウントする場所は間違えてないと思うのですが、出力の場所が悪いせいか、大量の出力結果が表示されます。 うまく表示させる方法を教えてください。 ～time.c～ #include <stdio.h> #include <stdlib.h> #include <time.h> #include "sfmt.h" #define MAX 5000 void quick_sort(int a[], int start, int end); main() { int i , x[MAX] , n; time_t start , end ; int sn; printf("適当な数字の入力 : "); scanf("%d", sn); init_gen_rand(sn); for(i=0; i<MAX; i++) x[i]= (gen_rand32()% MAX);; n=MAX; start = clock(); //測定対象プログラム quick_sort(x, 0, n-1); end = clock(); printf("sort\n"); for(i =0 ; i < n ; i++ ) if ( i == i/100*100) printf("%d\n" , x[i]); printf ("実行時間: %f sec\n" , (double)(end-start) /CLOCKS_PER_SEC); return 0; } ～quick.c～ #include <stdio.h> int hikaku = 0, koukan = 0; int divide_array(int x[], int start, int end) { int i, j, tmp; i = start; j = end -1; while(1){ while(x[i] < x[end])i++; hikaku++; //比較カウント while(x[j] > x[end] && j>i)j--; hikaku++; //比較カウント if(i >= j) break; tmp = x[i]; x[i] = x[j]; x[j] = tmp; koukan++; //交換カウント i++; j--; } tmp = x[i]; x[i] = x[end]; x[end] = tmp; printf("比較回数: %d\n", hikaku); printf("交換回数: %d\n", koukan); return i; } ～quick2.c～ int divide_array(int x[], int start, int end); void quick_sort(int a[], int start, int end); void quick_sort(int a[], int start, int end) { int s; if(start >= end) return; s = divide_array(a, start, end); quick_sort(a, start, s-1); quick_sort(a, s+1, end); }
- 締切済み
- C・C++・C#
- バブルソート：ポインタで並び替えについて。
今Ｃ言語の研修中で、バブルソートのプログラムをくんでいます。 それで、以下のように配列で入れ替えではなく、ポインタで入れ替えをしたいのですが、 dt+i = dt+i+1; dt+i+1 = dt2; で、 invalid lvalue in assignment というエラーが出てしまいます。 書き方がまちがっているんでしょうか？ 参考書やＨＰも探してみたのですが、探し方が悪いのかどうにもわかりません。 研修中なので、調べるのも勉強だとは思うのですが、お手上げで・・・・・・ 情けないですが、教えていただけると嬉しいです。 /** ソート処理 **/ static int SORT_PROC(void) { int i,m; syouhin_typ *dt2; /** バブルソートでソート処理 **/ for(m=0; m<i_cnt-1; m++){ for(i=0; i<i_cnt-1;i++){ if(strncmp((dt+i)->code,(dt+i+1)->code,sizeof(dt->code)) >= 0){ dt2 = dt+i; dt+i = dt+i+1; dt+i+1 = dt2; } } } } ちなみにdtはグローバル変数で、 typedef struct{ char code[5]; /** 商品コード **/ char uriage[5]; /** 売上数 **/ }syouhin_typ; /** グローバル変数 **/ syouhin_typ *dt; /** 商品 **/ としてあります。
- ベストアンサー
- C・C++・C#
補足
必ずそうはならないということは分りました。 http://ew.hitachi-system.co.jp/w/E382BBE383ACE382AFE382B7E383A7E383B3E382BDE383BCE38388.html などです。要素の数が同じであることが条件となっているようです。その場合は交換回数は同じなのでしょうか。