- ベストアンサー
バブルソート
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] の処理はいらないのではないのですか？ どのようにプログラムを書いたらいいのか教えて下さい。 あつかましいですが、できたら解説付きでお願いします。
- suzuno
- お礼率88% (88/100)
- Java
- 回答数3
- ありがとう数6
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
問題文がごちゃごちゃしすぎていますね。 まず、バブルソートは正式（？）には隣接交換法といいます。隣同士を順番に交換していきます。 一番泥臭く考えれば、右端から左端へ何回移動すれば整列が完了するでしょうか。 最も悪条件は左端に一番小さいデータがあって、これを右端へ移動させると考えると（Ｎ－１）回であることはすぐわかりますね。つまり、隣同士を比較しながらの右から左への移動（比較回数はＮ－１回）が（Ｎ－１）回で整列が完了する事になります。 ところが、これには無駄があります。右から左へ動いていくとき、必ず一番大きいデータが左端へ移動していきます。１回目は１番大きいデータ、２回目は２番目に大きいデータという風にです。従って、一番左に行ったデータは次からは比較の対象からはずしていいのです。（余談ですが大きい泡ほど早く水面に達するという現象になぞらえて、泡ソート＝バブルソートというあだ名がついています。） 従ってｆｏｒ文の２重ループが次の様になる事はお判りですね。 ｆｏｒ( )…比較の対象範囲の左端を管理するループ（ｉ＝０～Ｎ－２） （最低でも２個ないと比較できないので、Ｎ－１でなく，Ｎ－２） ｆｏｒ( )…１回ごとの比較の左端を管理するループ（ｊ＝（Ｎ－２）～ｉ） （これはｊ－－ である事に注意が必要です） ＞a[N-1] の処理はいらないのではないのですか？ いります。問題の書き方がよくないだけです。 a[N-1] と a[N-2] の比較からはじめて 一般形としてa[ j] と a[ j-1] の比較をする。逆転があれば入れ替える。という風に読まないといけないのです。 わかりにくい問題文で苦労させられているご様子、同情します。
その他の回答 (2)
- imogasi
- ベストアンサー率27% (4737/17068)
下記はＶＢＡでやって見ました。ご参考になれば。 何となく、質問の例の配列の要素（添え字）は理解し難い。 （Ｂ）のところは１回左より右へ比較が終わると、最小 が右のほうのＪ＋１番目に決まるので 第１回目 ０から５まで 第２回目 ０から４まで ・・・・ と１つずつ減っていく。 それで（Ａ）のところで５から１づつ減る変数ｊを５から ０まで１づつ減らしている。 Sub test01() a = Array(8, 45, 75, 90, 62, 73, 22) For j = 5 To 0 Step -1 '-----(A) For i = 0 To j '-------------(B) If a(i) > a(i + 1) Then Else W = a(i) a(i) = a(i + 1) a(i + 1) = W End If Next i Next j '------ For i = 0 To 6 Debug.Print a(i) Next i End Sub
お礼
お礼が遅れましてすみません。 わざわざのご回答ありがとうございました。 かかれてあることをちょっとずつ噛み締めて、なんとか成功することが出来ました。
- taka_tetsu
- ベストアンサー率65% (1020/1553)
これぐらいの個数でしたら、並びの変化を目で見ながら追っていくと理解しやすいですよ。 初期値 8,45,15,90,62,73,22 1回目 90,8,45,15,73,62,22 2回目 90,73,8,45,15,62,22 3回目 90,73,62,8,45,15,22 4回目 90,73,62,45,8,22,15 5回目 90,73,62,45,22,8,15 6回目 90,73,62,45,22,15,8 というように、最高6回のループでソートが完了します。 つまり、N-1回です。 (2)のN-2と書くとわかりづらいかもしれませんね。 for文で書くと、 for(i = 0; i < N-1; i++ ) こんな感じになります。 あと、バブルソートは、1回ループが終了するごとに先頭の値が決定するので比較の回数が1回ずつ少なくなっていくのがポイントです。 例： 2回目のループのとき、1回目で先頭にきた90と73の比較を行う必要はない。 こんな感じですかね。 バブルソートくらいですと、ソースを書くと答えになってしまうので・・・ そのまま書くと勉強にならないですし。
お礼
お礼が大変送れて申し訳ありません。 一から動きを確認し、少しずつ動かしていったらなんとか出来ました。 本当に初心者でお恥ずかしい。 ありがとうございました。
関連するQ&A
- 情報処理のバブルソートの問題について質問します。
情報処理のバブルソートの問題について質問します。 #include <stdio.h> int main(void) { double x[5]={6.0, 9.0, 2.0, 10.0, 8.0}; int i,j; int n=5; double temp; /* 初期状態の表示 */ printf("並べ替え前の並びは以下の通り：\n"); for (i=0; i<n; i++) { printf("%f,\t",x[i]); } printf("\n"); for (i=0; i<n-1; i++) { for (j=i+1; j<n; j++) { if (x[j] > x[i]) { temp = x[i]; x[i]=x[j]; x[j]=temp; } } } printf("大きい順に並べ替えた結果は以下の通り：\n"); for (i=0; i<n; i++) { printf("%f,\t",x[i]); } printf("\n"); return 0; } というプログラムを用いて行ってみたのですが、 これは王様ソートというプログラムだと言われました。 どのように換えればバブルソートになるのでしょうか？
- ベストアンサー
- その他（学問・教育）
- バブルソートで並べ替え
学校でC言語入門をやっています。今回「バブルソート」で配列の要素を降順（大きい順）に並べ替えるということをやっています。 バブルソートの原理はわかりましたが、書き方がよくわかりません。まず簡単な配列として、a[5]={5,2,24,8,31} というものを考えています。 for(k=0;k<n-1;k++){ if(a[k]<a[k+1]){ t=a[k];a[k]=a[k+1];a[k+1]=t; } } とすると、全範囲の中でバブルソートをおこなうので一番小さい"2"が a[4] に入り、位置の確定ができます。 今度は確定していない範囲でバブルソートをおこなうと for(m=0;m<k;m++){ if(a[m]<a[m+1]){ t=a[m];a[m]=a[m+1];a[m+1]=t; } } と先ほどと同様に書け、この中で一番小さい"5"が a[3] に確定します。以下同様に、範囲をせばめていきあと２つ for文を書くと全ての要素の位置が確定することになりますが、これは要素の数が多くなるととても大変なので複数の for文を１つのfor文でまとめたいのですがよくわかりません。 あと、バブルソートには上と下から(左と右から)の両方から査定する「カクテルシェイカソート」というものもあるらしいのですが、今回は一方向からの査定でやるという指示なのでよろしくお願いします。
- ベストアンサー
- C・C++・C#
- バブルソートを入れたいのですが
こんにちは、Perlを始めたばかりの初心者です。 さっそく質問の方失礼します。 乱数１～１００までの数字のうち20個をとりだし配列にいれ、数字を昇順に入れ替えして昇順前と昇順後の数字を表示する問題なのですが。 @a[100]=(1..100); srand(time()); for($i=0 ; $i<20 ; $i++){ $a=int(rand(@a)); print"$a\n"; } と上記の乱数20個を取り出すことができたのですが、 そのあとの昇順させようとしてバブルソートを利用したいのですが、どのように組み込めばいいかわかりません。 どのように組み込めばいいのでしょうか？ お答えの方ヨロシクお願いします。
- ベストアンサー
- Perl
- Cでのバブルソートがよくわかりません
C言語の課題でバブルソートのプログラミングをしています。入れるデータは10個で、降順に並び変えた最終的な結果だけでなく、毎回for文をまわす度にその時点での結果を表示させなければなりません。 そこで渡されたフローチャートを参考にしてプログラミングしてみたところ、以下のようになりました。しかしなかなか上手く行きません。C言語はまだまだ初心者なので、どなたかお力を貸していただけると助かります。 #include <stdio.h> main(){ int d[10] = {0,7,8,4,5,3,2,1,6,9}; int i,n,j,temp; for(i=1;i<j;i++){ for(j=1;j<=i;n--){ if(d[j]<d[j-1]){ temp=d[j]; d[j]=d[j-1]; d[j-1]=temp; } } for(i=0;i<=10;i++){ printf("%d ", d[i]); } } for(i=0;i<=10;i++){ printf("%d ", d[i]); } }
- ベストアンサー
- C・C++・C#
- マージソートについて
マージソートの要素の比較と交換回数を計測するプログラムを作っているのですが、マージのどの段階が交換処理になるのかが分からず困っています。 マージ処理の実行回数をカウントする配列ｓを設けて処理をカウントする場合、以下のプログラムだとどのタイミングでカウントすればよいでしょうか？ ちなみに配列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#
- javascript バブルソート
javascriptでバブルソートの実装をしています。 リストにある数値を取得して昇順 or 降順したいのですがうまくいきません。 方法を教えていただけないでしょうか。 よろしくお願いします。 <!DOCTYPE html> <html lang="ja"> <head> <meta charset="UTF-8"> <script type="text/javascript"> function bubbleSort(){ var liVal = document.getElementsByTagName("li"); var array = []; for(var i = 0; i < liVal.length; i++){ for(var j = 0; j < liVal.length-i-1; j++){ array[j] = parseInt(liVal[j].innerHTML); if(array[j] > array[j+1]){ var n = array[j]; array[j] = array[j+1]; array[j+1] = n; } } } } </script> </head> <body> <ul> <li>10</li> <li>5</li> <li>48</li> <li>22</li> <li>679</li> </ul> <p><a href="javascript:void(0);" onclick="bubbleSort()">ソート(降順)</a></p> </body> </html>
- 締切済み
- JavaScript
- バブルソートの実行時間について
バブルソートで降順、ランダム順に並んでいるデータを読み込ませて昇順に並び替える実行時間について質問です。 バブルソートにおける計算時間は、データ数が多いほど、並び替える回数が多いほど長くなるはずですが、実際に実行したところ、並び替える回数が多いはずの降順のほうがランダム順よりも早くなりました。 なぜこのようになるのですか？ よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 単純挿入ソートについて
単純挿入ソートの『選択』、『交換』、『挿入』の回数を出力せよ。という課題が出されたのですが意味がよくわかりません。ちなみに課題前に次のような説明をされました。 『選択』は交換と挿入を行うため、キー値等の比較を行う判定処理 『交換』は選択の結果、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・C++・C#
- クイックソートについて
下記のソースプログラムのquick_sort_coreの部分がわかりません。 わかる方助けてください。 あとこのソースを降順にした場合の変更点も教えていただけると助かります。 #include <stdio.h> /* printf()利用のため */ #include <stdlib.h> /* rand()利用のため */ #include <time.h> /* clock()利用のため */ #define N 10 /* 整列対象要素数 */ /** * 配列の中身を表示する関数 * @param a 表示する配列 * @param n 配列の要素数 */ void print_array(const int a[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } /** * 整列されているかどうか確認する関数 * @param a 確認対象配列 * @param n 配列の要素数 */ void is_sorted(const int a[], int n) { int i; for (i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { printf("昇順に整列されていません\n"); return; } } printf("昇順に整列されています\n"); } /** * クイックソートの本体 * @param a 整列対象配列 * @param l 対象の最初の要素番号 * @param r 対象の最後の要素番号 */ void quick_sort_core(int a[], int l, int r) { /* ここを実装する */ } /** * これまでの整列関数のインターフェースにあわせるクイックソート呼び出し関数 * @param a 整列対象配列 * @param n 配列の要素数 */ void quick_sort(int a[], int n) { quick_sort_core(a, 0, n - 1); } int main(void) { int i; int n = N; /* 整列対象要素数 */ int a[N]; clock_t start,end; /* 0からRAND_MAXの一様乱数をn個生成し、配列aに格納 */ for (i = 0; i < n; i++) { a[i] = rand(); /* 出力確認(print_array)するときは a[i]=rand()%100 としておくと見やすい */ } /* 昇順にソートされているか確認（デバッグ用） */ is_sorted(a, n); /* 配列の中身を確認（デバッグ用） */ print_array(a, n); /* 開始時刻の取得 */ start = clock(); /* クイックソート関数の呼び出し */ quick_sort(a, n); /* 終了時刻の取得 */ end = clock(); /* 配列の中身を確認（デバッグ用） */ print_array(a, n); /* 昇順にソートされているか確認（デバッグ用） */ is_sorted(a, n); /* 実行時間の表示 */ printf("%d 個の要素のクイックソートの実行に %f [秒]かかりました\n", n, (double)(end - start) / CLOCKS_PER_SEC); return 0; }
- 締切済み
- C・C++・C#
- java(バブルソート/単純挿入ソート)
以下のプログラムを「バブルソートもしくは単純挿入ソートのプログラムに変更しなさい」という課題が出ました。 どのようにすればよろしいでしょうか？ import java.util.*; public class SelectSort { //プログラムクラス名 //整列プログラム public static void main(String[] args){ //整列用 int 型配列 int[] target; int elems = KeyboardInput.askInt("要素数？ "); //配列を乱数で初期化する target = setArray(elems); //初期状態を表示 display(target); //整列メソッドの呼び出し sortArray(target); //整列結果の表示 display(target); } //配列を乱数で初期化するメソッド static int[] setArray(int elems){ // 要素数個の int 型変数の確保 int[] array = new int[elems]; //乱数利用ための宣言 Random generator = new Random(); //乱数の最大値・最小値 int max = 100; int min = 0; //generator.nextDouble() で 0から1までのdouble型乱数発生 for(int i=0 ; i<array.length ; i++) { array[i] = (int)((max-min)*(generator.nextDouble())+min); } return array; } //配列の状態を表示 static void display(int[] array){ for(int i=0 ; i<array.length ; i++) { System.out.print(array[i]+" "); } System.out.println(""); } static void sortArray(int[] array){ //配列のはじめから最後まで繰り返す for( int i = 0; i < array.length-1 ; i++){ int min_id = i; int min = array[i]; //範囲中でもっとも小さい要素を探す for( int j=i+1 ; j< array.length ; j++ ) { if( array[j] < min ){ min = array[j]; min_id = j ; } } //範囲の始めと置き換える int tmp = array[i]; array[i] = array[min_id]; array[min_id] = tmp; //display(array); } } }
- 締切済み
- Java
お礼
すみません、お礼が遅れました。 細かく、そしてわかりやすく説明してくださってありがとうございました。 読めば読むほどややこしくて…。 なんとか成功しました。